Cod sursa(job #1180811)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 1 mai 2014 10:40:14
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<fstream>
#include<string>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
string s,t;
int a[2000020],k=0,sol[1000000];
int main(){
	fi>>t>>s;
	int q=0;
	a[0]=0;
	for(int i=1;i<t.size();i++){
		while(q && t[q]!=t[i])q=a[q];
		if(t[q]==t[i])q++;
		a[i]=q;
	//	fo<<a[i]<<" ";
	}
//	fo<<endl;
	q=0;
	for(int i=1;i<s.size();i++){
		while(q && t[q]!=s[i])q=a[q];
		if(t[q]==s[i])q++;
		if(q==t.size()){
			sol[++k]=i-q+1;
			q=a[q-1];
			
		}
	}
	fo<<k<<endl;
	for(int i=1;i<=k && i<=1000;i++)fo<<sol[i]<<" ";
	
}