Cod sursa(job #1134263)

Utilizator span7aRazvan span7a Data 6 martie 2014 12:09:39
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<cstring>
#include<fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s1[2000005],s2[2000005];
int sar[2000005],n1,n2,nr,sol[1024];

void completeaza()
{
    for(int i=2;i<=n1;i++)
        if(s1[i-1]==s1[sar[i-1]])
            sar[i]=sar[i-1]+1;
        else if(s1[i-1]==s1[0]) sar[i]=1;
}
void kmp()
{
    int i,j,k=0,nrap=0;
    for(i=0;i<n2;)
    {
        j=0;k=i;
        while(j<n1&&k<n2&&s2[k]==s1[j]){k++;j++;}
        if(j==n1){nr++;if(nr<=1000)sol[++nrap]=i;}
        i=k-sar[j];
    }
    g<<nr<<'\n';
    for(i=1;i<=nrap;i++)
        g<<sol[i]<<" ";

}
int main()
{

    sar[0]=-1;sar[1]=0;
    f.getline(s1,2000005);
    f.getline(s2,2000005);
    n1=strlen(s1);
    n2=strlen(s2);
    completeaza();
    for(int i=0;i<=n1;i++)
        g<<sar[i]<<" ";
        g<<endl;
    kmp();
    return 0;
}