Cod sursa(job #1213146)

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

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,limit;
	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;
			}
			else ++aparitii;
		}
	}
	g<<aparitii<<"\n";
	limit=min(1000,aparitii);
	for(i=1;i<=limit;++i) g<<poz[i]<<" ";
	f.close();
	g.close();
	return 0;
}