Cod sursa(job #1416271)

Utilizator svasileVasile Sebastian svasile Data 7 aprilie 2015 19:44:25
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000005],B[2000005];
int pr[2000005],rez[2000005];
int i,q,n,m,nr,x;
int main()
{
    f>>A;
    f>>B;
n=strlen(A);
m=strlen(B);
nr=0;
q=0;x=0;
for(i=1;i<n;i++)
{
    while(q!=0&&A[q]!=A[i])
        q=pr[q-1];
    if(A[q]==A[i])
        q++;
    pr[i]=q;
}
q=0;
for(i=0;i<m;i++)
{
    while(q!=0&&A[q]!=B[i])
        q=pr[q];
    if(A[q]==B[i])
        q++;
    if(q==n)
    {
        q=pr[n-1];
        nr++;
        rez[x]=i-n+1;
        x++;
    }
}
    g<<nr<<endl;
if(x>999)
    x=999;
for(i=0;i<x;i++)
    g<<rez[i]<<" ";
    return 0;
}