Cod sursa(job #1196660)

Utilizator MarianMMorosac George Marian MarianM Data 8 iunie 2014 17:26:02
Problema Potrivirea sirurilor Scor 62
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <cstdio>
#include <fstream>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
#include <string>
#include <iterator>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

#define DMAX 2000001
#define MOD  140611
#define MOD2 1000000007
#define LIM  100000
#define MAX(a,b) a>b ? a : b

int D = 53, M, N, nrS, i, j;
char Px[DMAX], Tx[DMAX];
vector<int> S;

void match(int s){
	nrS++;
	if (nrS <= 1000) S.push_back(s);
}

inline int index(char c){
	return c >= 'A' && c <= 'Z' ? c - 'A' + 1 : 26 + c - 'a' + 1;
}
void RK (string P, string T){
	int hashP(0), hashT(0), hashD(1);

	for (i = 0; i < M; i++){
		hashP *= D, hashP += index(P[i]), hashP %= MOD;
		hashT *= D, hashT += index(T[i]), hashT %= MOD;
		if (i) hashD *= D, hashD %= MOD;
	}

	for (i = 0; i <= N - M; i++){
		if (hashT == hashP) match(i);
		hashT = ((hashT + D*MOD - index(T[i]) * hashD)\
			% MOD*D + index(T[i + M])) % MOD;
	}
}

void BM (string P, string T){
	int skip;
	vector<int> Right(D, -1);

	for (i = 0; i < M; i++)	Right[index(P[i])] = i;
	
	for (i = 0; i <= N - M; i += skip){
		skip = 0;
		for (j = M - 1; j >= 0; j--){
			if (P[j] != T[i+j]){
				skip = j - Right[index(T[i + j])];
				skip = MAX(1, skip);
				break;
			}
		}
		if (skip == 0) match(i), skip = 1;
	}
	
}

void KMP(string P, string T){
	int maxps(0), k;
	vector<int> Pattern(M + 1, 0);

	Pattern[0] = -1;
	for (i = 1; i<=M; i++){
		k = Pattern[i - 1];
		while (k != -1 && P[i - 1] != P[k])		
			k = Pattern[k];
		Pattern[i] = k + 1;
	}

	for (i = j = 0; i < N; i++){
		while (j >= 0 && P[j] != T[i])	j = Pattern[j];
		if (++j == M) match(i - M + 1), j = Pattern[j];
	}
}

void write(){
	printf("%d\n", nrS);
	for (i = 0; i < 1000 && i < nrS; i++){
		printf("%d ", S[i]);
	}
}

int main(){

	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	scanf("%s\n%s", Px, Tx);

	string P(Px), T(Tx);
	M = P.size(); N = T.size();

	//RK(P, T);
	//KMP(P, T);
	//BM(P, T);

	if (M > N) printf("0\n");
	else if (P.size() <= 3  ) RK (P, T);
	//else if (P.size() <= LIM) KMP(P, T);
	else BM (P, T);

	write();

	return 0;

}