Cod sursa(job #1213112)

Utilizator IulianBoboUAIC Boboc Iulian IulianBobo Data 27 iulie 2014 11:38:58
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;
char s1[2000001],s2[2000001];
int phi[2000001],poz[2000001];

void computePhi(char *s)
{
	long i,k,n;
	k=-1;
	phi[0]=0;
	n=strlen(s);
	for(i=1;i<n;++i)
	{
		while(k>-1 && 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");
	long aparitii=0;
	long i,k,n,m;
	f.getline(s1,2000002);
	f.getline(s2,2000002);
	n=strlen(s1);
	m=strlen(s2);
	computePhi(s1);
	k=-1;
	for(i=0;i<m;++i)
	{
		while(k>-1 && s1[k+1]!=s2[i])
			k=phi[k];
		if(s1[k+1]==s2[i]) ++k;
		if(k==n-1)
			poz[++aparitii]=i-n+1;
	}
	g<<aparitii<<"\n";
	for(i=1;i<=aparitii;++i) g<<poz[i]<<" ";
	f.close();
	g.close();
	return 0;
}