Cod sursa(job #1468420)

Utilizator dimavascan94VascanDumitru dimavascan94 Data 6 august 2015 00:11:40
Problema Potrivirea sirurilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 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;
	j=0;
	while (i+j<text.size())
	{
		if (text[i+j]==pattern[j])
		{
			if (j==pattern.size()-1)
			{
				matches[nmbMatches]=i;
				nmbMatches++;
				j=f[j];
			}
			else
			{
				j++;
			}
		}
		else
		{
			while (f[j]!=-1 && pattern[j]!=text[i+j])
			{
				j=f[j];
			}
			
			if (f[j]==-1) j=0,i++;
									
		}
	}
	
	cout<<nmbMatches<<"\n";
	for (i=0;i<nmbMatches;i++)
	{
		cout<<matches[i]<<" ";
	}
	
}