Cod sursa(job #627217)

Utilizator unsilviuContvechidontdeactivatepls unsilviu Data 29 octombrie 2011 12:33:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <string>
using namespace std;
string s,x;
int pr[2000001],k,prv[2000001];
int n,i,j,pot,xl,sl;
int main() {
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f>>x>>s;
	for (i=s.length(); i>=1; i--)
		s[i]=s[i-1];
	for (i=x.length(); i>=1; i--)
		x[i]=x[i-1];
	xl=x.length();
	sl=s.length();
	for (i=2; i<=xl; i++) {
		k=pr[i-1];
		while(k&&x[k+1]!=x[i]) 
		k=pr[k];
		if (x[k+1]==x[i])
			k++;
		pr[i]=k;
	}
	k=0;
	for (i=1;i<=sl;i++) {
		while(k&&x[k+1]!=s[i])
			k=pr[k];
		if (x[k+1]==s[i])
			k++;
		if (k==xl) {
			pot++;
			if (pot<=1000)
				prv[pot]=i-xl;
		}	
	}
	g<<pot<<'\n';
	for (i=1; i<=min(pot,1000); i++)
		g<<prv[i]<<' ';
	g.close();
	return 0;
}