Cod sursa(job #966276)

Utilizator dropsdrop source drops Data 25 iunie 2013 16:51:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include <string>
#include <algorithm>
using namespace std;
ifstream ff("strmatch.in");
ofstream gg("strmatch.out");

string pp, ss;
int uu[2000001], w;
vector<int> vv;

void pfx(){
	int k = 0, l = pp.length();
	uu[1] = 0;
	for(int i=2;i<l;i++){
		while(k>0 && pp[k+1]!=pp[i])k=uu[k];
		if(pp[k+1]==pp[i])k++;
		uu[i]=k;
	}
}

void kmp(){
	int k = 0, l = ss.length(), n = pp.length();
	for(int i=1;i<l;i++){
		while(k>0 && pp[k+1]!=ss[i])k=uu[k];
		if(pp[k+1]==ss[i])k++;
		if(k==n-1){
			w++;
			if(w<=1000)vv.push_back(i-k);
			k=uu[k];
		}
	}
}

int main(){
	ff >> pp >> ss;
	pp = " " + pp;
	ss = " " + ss;
	pfx();
	kmp();
	gg << w << "\n";
	int l = vv.size();
	for(int i=0;i<l;i++) gg << vv[i] << " ";
	return 0;
}