Cod sursa(job #850411)

Utilizator misinozzz zzz misino Data 8 ianuarie 2013 15:07:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int i,n,m,nr,v[2000009],urm[2000009];
char s1[2000009],s2[2000009];
void prefix(char s1[])
{
    int i,k=-1;
    urm[0]=-1;
    for(i=1;i<n;++i)
    {
        while(k!=-1&&s1[i]!=s1[k+1])
        k=urm[k];
        if(s1[i]==s1[k+1])
        ++k;
        urm[i]=k;
    }
}
void kmp(char s2[],char s1[])
{
    int i,k=-1;
    for(i=0;i<m;++i)
    {
        while(k!=-1&&s2[i]!=s1[k+1])
        k=urm[k];
        if(s2[i]==s1[k+1])
        ++k;
        if(k==n-1)
        ++nr,v[nr]=i-n+1,k=urm[k];
    }
}
int main()
{
    f>>s1>>s2;
    n=strlen(s1);
    m=strlen(s2);
    prefix(s1);
    kmp(s2,s1);
    g<<nr<<'\n';
    nr=min(nr,1000);
    for(i=1;i<=nr;++i)
    g<<v[i]<<' ';
    return 0;
}