Cod sursa(job #899486)

Utilizator vgabi94Vaduva Gabriel vgabi94 Data 28 februarie 2013 14:47:36
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <cstring>
using namespace std;
// Knuth-Morris-Pratt
ifstream in("strmatch.in");
ofstream out("strmatch.out");

const int maxn = 2000002;

char A[maxn], B[maxn];
int F[maxn], pos[1000]; // F - Failure function
int M, N;

void buildFunction()
{
    F[0] = -1; int j = -1;
    for (int i = 0; i < M; i++)
    {
        while (j >= 0 && A[i] != A[j])
            j = F[j];
        j++;
        F[i] = j;
    }
}

int KMPmatch(int start)
{
    int i, j;
    for (i = start, j = 0; i < N && j < M; i++, j++)
    {
        while (j >= 0 && B[i] != A[j])
            j = F[j];
    }
    if (j == M) return i - M + 1;
    else return i;
}

int main()
{
    in.getline(A, maxn);
    in.getline(B, maxn);
    N = strlen(B);
    M = strlen(A);
    buildFunction();
    int poz = 0, k = 0;
    while (true)
    {
        poz = KMPmatch(poz);
        if (poz > 0 && poz < N) pos[k++] = poz;
        else break;
    }
    out << k << '\n';
    int max = (k > 1000 ? 1000 : k);
    for (int i = 0; i < max; i++) out << pos[i] << ' ';

    return 0;
}