Cod sursa(job #1213140)

Utilizator IulianBoboUAIC Boboc Iulian IulianBobo Data 27 iulie 2014 12:24:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;
string s1,s2;
int phi[2000001],poz[1001];

void computePhi(string s,long size)
{
	int i,k;
	k=0;
	phi[1]=0;
	for(i=2;i<size;++i)
	{
		while(k>0 && s[k+1]!=s[i])
			k=phi[k];
		if(s[k+1]==s[i]) ++k;
		phi[i]=k;
	}
}
int main()
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	int aparitii=0;
	int i,k,n,m;
	f>>s1>>s2;
	s1.insert(0," ");
	s2.insert(0," ");
	n=s1.size();
	m=s2.size();
	computePhi(s1,n);
	k=0;
	for(i=1;i<m;++i)
	{
		while(k>0 && s1[k+1]!=s2[i])
			k=phi[k];
		if(s1[k+1]==s2[i]) ++k;
		if(k==n-1)
		{
			if(aparitii<=1000)
			{
				poz[++aparitii]=i-n+1;
			}
		}
	}
	g<<aparitii<<"\n";
	for(i=1;i<=aparitii;++i) g<<poz[i]<<" ";
	f.close();
	g.close();
	return 0;
}