Cod sursa(job #1678224)

Utilizator ticozaurStratila Andrei ticozaur Data 7 aprilie 2016 09:46:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int nextt[2000001],n,m,nr,sol[1001];
char P[2000001],T[2000001];
void urm(char *P)
{
    int k=-1;
    nextt[0]=0;
    for(int i=1; i<m; i++)
    {
        while(k>0 && P[k+1]!=P[i])
            k=nextt[k];
        if(P[k+1]==P[i])
            k++;
        nextt[i]=k;
    }
}
int main()
{
    int x=-1;
    fin>>P>>T;
    n=strlen(T);
    m=strlen(P);
    urm(P);
    for(int i=0; i<n; i++)
    {
        while(x>0 && P[x+1]!=T[i])
            x=nextt[x];
        if(P[x+1]==T[i])
            x++;
        if(x==m-1)
        {
            nr++;
            if(nr<1001)
                sol[nr]=i-m+1;
            x=nextt[x];
        }
    }
    fout<<nr<<'\n';
    for(int i=1; i<=min(nr,1000); i++)
        fout<<sol[i]<<' ';
    fout<<'\n';
    return 0;
}