Cod sursa(job #2290054)

Utilizator gabiluciuLuciu Gabriel gabiluciu Data 25 noiembrie 2018 18:22:20
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 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;
    int cnt = 0;
    vector<int> sol;
    for(auto i =0;i<m;++i){
        while (b[i]!=a[j+1]){
            if(j==-1) break;
            j = v[j];
        }
        if(b[i] == a[j+1]) ++j;
        if(j == n-1) {
            cnt++;
            if(cnt<=1000)
            sol.push_back(i-n+1);
        }
    }
    cout << cnt << nl;
    j = 1;
    for_each(sol.begin(),sol.end(),[](auto n){cout << n << ' ';});
    /*
    for(auto i=0;i<n;++i){
        cout << v[i] << ' ';
    }
    */
    return 0;
}