Cod sursa(job #961393)

Utilizator Anca_PaneaPanea Anca Anca_Panea Data 11 iunie 2013 23:49:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
using namespace std;
#include<stdio.h>
#include<cstring>
#include<vector>
#include<fstream>
ifstream eu("strmatch.in");
ofstream tu("strmatch.out");
 vector<int>::iterator it;
vector<int>Sol;
char A1[2000005],A2[2000005];
int P[2000005],i,j,q,M,N,k,Solutie;
void construim_prefixul()
{
    M=strlen(A1)-1;
    P[0]=P[1]=0;
    for(i=2;i<=M;i++)
    {
        while(k&&A1[k+1]!=A1[i])
			k=P[k];
		if(A1[i]==A1[k+1])
			k++;
		P[i]=k;
    }
	
}
void KMP()
{
    construim_prefixul();
    N=strlen(A2)-1;
    for(i=1;i<=N;++i)
	{
		while(q&&A2[i]!=A1[q+1])
			q=P[q];
		if(A2[i]==A1[q+1])
			++q;
		if(q==M)
		{
			q=P[M];
            Solutie++;
					if(Solutie<=1000)
						Sol.push_back(i-M);
		}
	}
}
int main()
{
	A1[0]=' ';
	A2[0]=' ';
	eu>>A1+1;
	eu>>A2+1;
    KMP();
    tu<<Solutie<<"\n";
	for(it=Sol.begin();it!=Sol.end();++it)
		 tu<<*it<<" ";
    return 0;}