Cod sursa(job #762250)

Utilizator ioanabIoana Bica ioanab Data 29 iunie 2012 15:44:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

const int N=2000010;
char a[N],s[N];

int prefix[N],rez[N];

void kmp()
{
    int m=strlen(a+1),i,j;
    prefix[0]=-1;
    
	for (i=2;a[i];i++)
        for (int j=prefix[i-1];j>=0;j=prefix[j])
            if (a[j+1]==a[i])
            {
                prefix[i]=j+1;
                break;
            }
			
    for (i=1, j=-1;s[i];i++)
        for (j++;j>=0;j=prefix[j])
            if (a[j+1]==s[i])
            {
                if (j==m-1)
                    rez[++rez[0]]=i-m;
                break;
            }
}

int main()
{
   
	in>>a+1>>s+1;

    kmp();
    out<<rez[0]<<"\n";

    rez[0]=min(rez[0],1000);
    for (int i=1;i<=rez[0];i++)
        out<<rez[i]<<" ";
	
    out<<"\n";
    return 0;
}