Cod sursa(job #1045912)

Utilizator KostynGraur Petru-Costin Kostyn Data 2 decembrie 2013 12:27:17
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
char s1[2000001],s2[2000001];
int pi[2000001],poz[1001];
void citire()
{
	ifstream f("strmatch.in");
	f>>s1;
	f.get();
	f>>s2;
	f.close();
}
void prefix()
{
	int n=strlen(s1)-1;
	pi[1]=0;
	int k=0;
	for(int i=1;i<=n;i++)
	{
		while((k>0)&&(s1[k+1]!=s1[i]))k=pi[k];
		if(s1[k+1]=s1[i])
		k=k+1;
		pi[i]=k;
	}
}
int subsiruri()
{
	int i,n=0,k=0;
	prefix();
	for(i=0;i<strlen(s2);i++)
	{
		while((k>=0)&&(s1[k+1]!=s2[i]))k=pi[k];
		if(s1[k+1]==s2[i])k++;
		if(k==strlen(s1)-1)
		{
			k=pi[k];
			n++;
			if(n<=1000)poz[n]=i-strlen(s1)+1;
		}
	}
	return n;
}
void afisare(int n)
{
	ofstream g("strmatch.out");
	g<<n<<endl;
	for(int i=1;i<=n;i++)
		g<<poz[i]<<" ";
}
int main()
{
	citire();
	int n=subsiruri();
	afisare(n);
	return 0;
}