Cod sursa(job #1468410)

Utilizator dimavascan94VascanDumitru dimavascan94 Data 5 august 2015 23:45:18
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <string.h>
using namespace std;

int f[2000005],i,j,nmbMatches=0,matches[1005],k;
string pattern,text;

int main()
{
	freopen ("strmatch.in","r",stdin);
	freopen ("strmatch.out","w",stdout);
	
	cin>>pattern>>text;
	
	f[0]=-1;
	
	for (i=1;i<pattern.size();++i)
	{
		k=f[i-1];
		while (k!=-1 && pattern[k]!=pattern[i-1])
			k=f[k];
		f[i]=k+1;
	}
	
	i=0;
	while (i<text.size())
	{
		while (j!=-1 && text[i]!=pattern[j])
			j=f[j];
		if (j==pattern.size()-1)
		{
			matches[nmbMatches]=i-j;
			nmbMatches++;
			if (nmbMatches==1000)
				break;
			j=0;
		}
		else
		{
			i++;
			j++;
		}
	}
	
	cout<<nmbMatches<<"\n";
	for (i=0;i<nmbMatches;i++)
	{
		cout<<matches[i]<<" ";
	}
	
}