Cod sursa(job #639332)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 23 noiembrie 2011 02:42:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 3.17 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <iomanip>
#include <fstream>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define oo (1<<30)
#define f first
#define s second
#define II inline
#define db double
#define ll long long
#define pb push_back
#define mp make_pair
#define Size(V) ((ll)(V.size()))
#define all(V) (V).begin() , (V).end()
#define CC(V) memset((V),0,sizeof((V)))
#define CP(A,B) memcpy((A),(B),sizeof((B)))
#define FOR(i,a,b) for(int (i)=(a);(i)<=(b);++(i))
#define REP(i, N) for (int (i)=0;(i)<(int)(N);++(i))
#define FORit(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define printll(x) printf("%lld",(x))
#define printsp() printf(" ")
#define newline() printf("\n")
#define readll(x) scanf("%lld",&(x))
#define debugll(x) fprintf(stderr,"%lld\n",(x))

#define IN "strmatch.in"//"code.in"
#define OUT "strmatch.out"//"code.out"
#define S_MAX (1<<21)

typedef vector<int> VI;
typedef pair<int,int> pi;
typedef pair<short int,short int> ps;
typedef vector<string> VS;
template<class T> string toString(T n) {ostringstream ost;ost<<n;ost.flush();return ost.str();}

int M, N;
char S1[S_MAX], S2[S_MAX];
int KmpPi[S_MAX], pos[1024];
char match[S_MAX];

II bool isAlpha(char ch)
{
    return !(ch == ' ' || ch == '\n');
}

II VI KMP(int M,int N)
{
    VI Sol;
	int rem = 0;
    KmpPi[1] = 0;

	FOR(i,2,M)
	{
		while (rem && S1[rem + 1] != S1[i])
			rem = KmpPi[rem];
		if (S1[rem + 1] == S1[i])
			++rem;
		KmpPi[i] = rem;
	}

    rem = 0;
	FOR(i,1,N)
	{
		while (rem && S1[rem + 1] != S2[i])
			rem = KmpPi[rem];
		if (S1[rem + 1] == S2[i])
			++rem;
		if (rem == M)
		{
			rem = KmpPi[M];
			if ( Size(Sol) < 1000)
				Sol.pb(i - M);
		}
	}

    return Sol;
}

II VI RabinKarp(int N,int M)
{
    #define P 73
    #define MOD1 100007
    #define MOD2 100021

    VI Sol;
    int P1 = 1,P2 = 1;
	int hashA1 = 0,hashA2 = 0;
    int hash1 = 0,hash2 = 0;

	FOR(i,1,N)
	{
		hashA1 = (hashA1 * P + S1[i]) % MOD1;
		hashA2 = (hashA2 * P + S1[i]) % MOD2;

		if (i != 1)
			P1 = (P1 * P) % MOD1,
			P2 = (P2 * P) % MOD2;
	}

	if (N > M)
	{
		printf("0\n");
		return Sol;
	}

	FOR(i,1,N)
		hash1 = (hash1 * P + S2[i]) % MOD1,
		hash2 = (hash2 * P + S2[i]) % MOD2;

	int Nr = 0;
	if (hash1 == hashA1 && hash2 == hashA2)
		match[0] = 1;

	FOR(i,N + 1,M)
	{
		hash1 = ((hash1 - (S2[i - N] * P1) % MOD1 + MOD1) * P + S2[i]) % MOD1;
		hash2 = ((hash2 - (S2[i - N] * P2) % MOD2 + MOD2) * P + S2[i]) % MOD2;

		if (hash1 == hashA1 && hash2 == hashA2)
			match[ i - N ] = 1;
	}

	FOR(i,1,M)
        if(match[i] && Size(Sol) < 1000)
            Sol.pb(i);

    return Sol;
}

int main(void)
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);

	fgets(S1 + 1, S_MAX, stdin);
	fgets(S2 + 1, S_MAX, stdin);
	for (++N; isAlpha(S1[N + 1]); ++N);
	for (++M; isAlpha(S2[M + 1]); ++M);

	VI Sol = KMP(N, M);
    //VI Sol = RabinKarp(N,M);

	printf("%d\n", Size(Sol) );
	FORit(it,Sol)
		printf("%d ", *it);
	printf("\n");

	return 0;
}