Cod sursa(job #344858)

Utilizator digital_phreakMolache Andrei digital_phreak Data 31 august 2009 20:03:05
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 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 <cstring>
#include <string>
#include <ctime>
using namespace std;

long T[2100000];
char s1[2100000],s2[2100000];
long matches[1024];
long cntmatch;
int M,N;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

void make_table() {
	T[0] = -1;
	T[1] = 0;
	int pos = 2,cnd = 0;
	
	while (pos < M) {
		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;
	cntmatch = 0;
	while (m + i < N) {
		if (s2[i] == s1[m + i]) {
			++i;
			if (i == M) {
				if (cntmatch < 1000)
					matches[cntmatch++] = m;
				else 
					cntmatch++;
				if (i > 0) i = T[i];
				++m;
			}
		} else {
			m = m + i - T[i];
			if (i > 0) i = T[i];
		}
	}
	return N;
}

bool isalphachar(char c) {
	return (((c >= 'A') && (c <= 'Z')) || ((c >= 'a') && (c <= 'z')) || ((c>='0') && (c<='9')));
}

int main() {

	ios::sync_with_stdio(false);
	
	fin >> s2;
	fin >> s1;
	
	cerr << clock() << endl;
	
	M = 0;
	N = 0;
	
	for (;isalphachar(s2[M]);++M);
	for (;isalphachar(s1[N]);++N);
	
	make_table();
	search_string();
	
	fout << cntmatch << "\n";
	
	int k = (cntmatch > 1000) ? 1000 : cntmatch;
	for (int i=0;i<k;++i) fout << matches[i] << " ";
		
	fin.close();
	fout.close();
	
	return 0;
}