Cod sursa(job #2290038)

Utilizator gabiluciuLuciu Gabriel gabiluciu Data 25 noiembrie 2018 18:08:43
Problema Potrivirea sirurilor Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define nl '\n'
using namespace std;
int v[2000002];
char a[2000002];
char b[2000002];
int main() {
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    cin >> a >> b;
    auto n = strlen(a),m=strlen(b);
    v[0] = -1;
    auto j = 0;
    for(auto i=0;i<n;){
        j = 0;
        ++i;
        while (a[i] == a[j]) {
            v[i] = j;
            ++i;
            ++j;
        }
        v[i] = -1;
    }
    j = 0;
    vector<int> sol;
    for(auto i =0;i<m;++i){
        while (b[i]!=a[j+1]){
            if(!j) break;
            j = v[j];
        }
        if(b[i] == a[j+1]) ++j;
        if(j == n-1) {
            sol.push_back(i-n+1);
        }
    }
    cout << sol.size() << nl;
    for_each(sol.begin(),sol.end(),[](auto n){cout << n << ' ';});
    /*
    for(auto i=0;i<n;++i){
        cout << v[i] << ' ';
    }
    */
    return 0;
}