Cod sursa(job #2375469)

Utilizator netfreeAndrei Muntean netfree Data 8 martie 2019 09:45:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda pregatire_cls12_oji Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");

const int N_MAX = 2000000 + 5;

char P[N_MAX], T[N_MAX];
int key[N_MAX];

void build_key(){
    int m = strlen((P+1));
    int k = 0;
    for(int i = 2; i <=m; ++i){
        while(P[i] != P[k+1] and k > 0)
            k = key[k];
        if(P[i] == P[k+1])
            k++;
        key[i] = k;
    }
}

int ans;
vector<int> vecans;

void kmp(){
    int n = strlen(T+1), m = strlen(P+1);
    int k = 0;
    for(int i = 1; i <=n; ++i){
        while(T[i] != P[k+1] and k > 0)
            k = key[k];
        if(T[i] == P[k+1])
            k++;

        if(k == m){
            ans++;
            if(ans < 1000)
                vecans.push_back(i-m);
            k = key[k];
        }

    }

}

int main()
{
    fin >> (P+1);
    fin >> (T+1);

    build_key();
    kmp();

    fout << ans << "\n";
    for(auto v :vecans)
        fout << v << " ";

    fin.close();
    fout.close();

    return 0;
}