Cod sursa(job #1524029)

Utilizator Iustin48Ventaniuc Iustin Iustin48 Data 13 noiembrie 2015 15:11:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char P[2000001],T[2000001];
int L[2000001],n,m,k,nr,sol[1001];
int main()
{
    f>>P+1;
    f>>T+1;
    P[0]='a';
    T[0]='a';
    m=strlen(P)-1;
    n=strlen(T)-1;
    L[1]=0;
    for(int i=2;i<=m;++i)
    {
        L[i]=L[i-1];
        while(L[i]&&P[L[i]+1]!=P[i])
            L[i]=L[L[i]];
        if(P[L[i]+1]==P[i])
            ++L[i];
    }
    for(int i=1;i<=n;++i)
    {
        while(k&&P[k+1]!=T[i])
            k=L[k];
        if(P[k+1]==T[i])
            ++k;
        if(k==m)
        {
            if(nr<=1000)
                sol[++nr]=i-m;
            else
                ++nr;
            k=L[k];
        }
    }
    g<<nr<<'\n';
    nr=min(nr,1000);
    for(int i=1;i<=nr;++i)
        g<<sol[i]<<" ";
    return 0;
}