Cod sursa(job #1561769)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 4 ianuarie 2016 15:28:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 2000050

using namespace std;

char A[MAXN], B[MAXN];
int pi[MAXN], n, m, sol[1010];

void citire()
{
    gets(A);
	n = strlen(A);
    for (int i = n; i >= 1; i--)
		A[i] = A[i-1];
    gets(B);
	m = strlen(B);
    for (int i = m; i >= 1; i--)
		B[i] = B[i-1];
}

void init()
{
	/// Calculam prefixele pentru A
    int k = 0;
    pi[1] = 0;
    for (int i = 2; i <= n; i++) {
		while (A[i] != A[k+1] && k)
			k = pi[k];
		if (A[i] == A[k+1])
			k++;
		pi[i] = k;
    }
    /// debug
//    for (int i = 1; i <= n; i++)
//		printf("%d ", pi[i]);
}

void newSolution(int ind)
{
	sol[0]++;
    if (sol[0] <= 1000)
		sol[sol[0]] = ind-n+1;
}

void solve()
{
    /// KMP
    int k = 0;
    for (int i = 1; i <= m; i++) {
		while (B[i] != A[k+1] && k)
			k = pi[k];
        if (B[i] == A[k+1])
			k++;
		if (k == n)
			newSolution(i);
    }
}

void print()
{
	printf("%d\n", sol[0]);
    for (int i = 1; i <= sol[0] && i <= 1000; i++)
		printf("%d ", sol[i]-1);
}

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

	citire();
	init();
	solve();
	print();

    return 0;
}