Cod sursa(job #1135301)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 7 martie 2014 17:41:08
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define DN 2000003
#define DM 1004
using namespace std;

char p[DN],t[DN];
int pi[DN],rez[DN],kk;

void make_p(){

	pi[1]=0;
	int k = 0;
	for(int i=2;i<=strlen(p+1);++i){
		
		while(p[i] != p[k+1] && k>0)
			k = pi[k];
		if(p[i] == p[k+1])
			++k;
		pi[i] = k;
	}
}

int main() {
		
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	cin>>p+1>>t+1;	
	make_p();
	
	int i=1,j=1,n=strlen(t+1),m=strlen(p+1);
	
	for(;i<=n && j<=m;){
			
			if(t[i] == p[j]) ++i,++j;
			else
				if(j==1) ++i;
					else
					 j = pi[j-1] + 1;
			if(j == m + 1){
				
				rez[++rez[0]] = i-m-1;

				j=pi[j-1]+1;
			}
	}
	g<<rez[0]<<"\n";
	for(int i=1;i<=min(1000,rez[0]);++i)
		g<<rez[i]<<" ";
	return 0;
}