Cod sursa(job #852869)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 11 ianuarie 2013 21:06:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <cstring>
using namespace std;
string P, S;
int k, m, n, sol, pi[2000010], i, t, a[1010];
void prefix()
{
    k = 0;
    for(i = 2; i <= n; i++)
    {
        while(k and P[k+1] != P[i]) k = pi[k];
        if(P[k+1] == P[i]) k++;
        pi[i] = k;
    }
}
void go()
{
    k = 0;
    for(i = 1; i <= m; i++)
    {
        while(k and P[k+1] != S[i]) k = pi[k];
        if(P[k+1] == S[i]) k++;
        if(k == n and sol < 1000) a[++t] = i - n;
        if(k == n) sol++;
    }
}
int main()
{
    ifstream fi("strmatch.in");
    ofstream fo("strmatch.out");
    fi >> P >> S;
    n = P.length();
    m = S.length();
    P = " " + P;
    S = " " + S;
    prefix();
    go();
    fo << sol << "\n";
    for(i = 1; i <= t; i++) fo << a[i] << " ";
    return 0;
}