Cod sursa(job #2169321)

Utilizator netfreeAndrei Muntean netfree Data 14 martie 2018 14:46:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 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], ans;
vector<int> sol;

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

void kmp(){
    build_key();
    int k = 0, n = strlen(T + 1), m = strlen(P + 1);
    for(int i = 1; i<=n; ++i){
        while(P[k + 1] != T[i] and k > 0)
            k = key[k];
        if(P[k + 1] == T[i])
            k ++;
        if(k == m){
            ans ++;
            if(sol.size() < 1000)
                sol.push_back(i - m);
            k = key[k];
        }
    }
}

int main()
{
    fin >> (P + 1);
    fin >> (T + 1);
    kmp();
    fout << ans << "\n";
    for(auto i : sol)
        fout << i << " ";
    return 0;
}