Cod sursa(job #1524119)

Utilizator mantisVraciu Stefan mantis Data 13 noiembrie 2015 16:12:55
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<cstring>
#include<algorithm>
#define DMAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char T[DMAX],P[DMAX];
int n,m,nr,L[DMAX],sol[1005];
void prefix()
{
    int k=-1;
    L[0]=0;
    for(int i=1;i<m;i++)
    {
        while(k>=0 and P[k+1]!=P[i]) k=L[k];
        if(P[k+1]==P[i]) k++;
        L[i]=k;
    }
}
void KMP()
{
    int k=-1;
    for(int i=0;i<n;i++)
    {
        while(k>0 and P[k+1]!=T[i]) k=L[k];
        if(P[k+1]==T[i]) k++;
        if(k==m-1)
        {
            nr++;
            if(nr<=1000) sol[nr]=i-m+1;
            k=L[k];
        }
    }
}
int main()
{
    f>>P;
    f>>T;
    m=strlen(P);
    n=strlen(T);
    prefix();
    KMP();
    g<<nr<<'\n';
    nr=min(nr,1000);
    for(int i=1;i<=nr;i++)
        g<<sol[i]<<' ';
    g.close();
    return 0;
}