Cod sursa(job #342516)

Utilizator digital_phreakMolache Andrei digital_phreak Data 22 august 2009 09:59:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
//Implementation of Knuth-Morris-Prat Algorithm
//Input s1,s2 
//Output first position of s2 in s1

#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <string>

using namespace std;

int T[2000000];
int matches[2000000];
int cntmatch;
string s1,s2;

void make_table() {
	T[0] = -1;
	T[1] = 0;
	int pos = 2,cnd = 0;
	
	while (pos < s2.length()) {
		if (s2[pos - 1] == s2[cnd]) T[pos] = cnd + 1 , ++pos , ++cnd;
		else if(cnd > 0) cnd = T[cnd];
		else T[pos]=0, ++pos;
	}
	
}

int search_string() {
	int i,m;
	i = m = 0;
	
	while (m + i < s1.length()) {
		if (s2[i] == s1[m + i]) {
			++i;
			if (i == s2.length()) {
				matches[cntmatch++] = m;
				i = 0;
				++m;
			}
		} else {
			m = m + i - T[i];
			if (i > 0) i = T[i];
		}
	}
	
	return s1.length();
}

int main() {

	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	
	getline(fin,s2);
	getline(fin,s1);
	
	make_table();
	
	search_string();
	
	fout << cntmatch << endl;
	for (int i=0;i<min(1000,cntmatch);++i) fout << matches[i] + 1 << " ";
	fout << endl;
		
	fin.close();
	fout.close();
		
	return 0;
}