Cod sursa(job #342729)

Utilizator digital_phreakMolache Andrei digital_phreak Data 23 august 2009 10:06:04
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.58 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>

using namespace std;
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

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

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;
}

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

int main() {

	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
		
	fgets(s2,sizeof(s2),stdin);
	fgets(s1,sizeof(s1),stdin);

	M = 0;
	N = 0;
	
	for (;isalphachar(s2[M]);++M);
	for (;isalphachar(s1[N]);++N);
		
	make_table();
	search_string();
	
	printf("%ld\n",cntmatch);
	
	int k = (cntmatch > 1000) ? 1000 : cntmatch;
	
	for (int i=0;i<k;++i) printf("%ld ",matches[i]);
		
	fclose(stdin);
	fclose(stdout);
		
	return 0;
}