Cod sursa(job #899655)

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

const int maxn = 2000100;

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

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

void KMPmatch()
{
    int q = 0;
    for (int i = 1; i <= M; i++)
    {
        while (q > 0 && A[q+1] != B[i])
            q = F[q];
        if (B[i] == A[q+1]) q++;
        if (q == N)
        {
            k++;
            if (k <= 1000)
                pos[k] = i - N;
        }
    }

}

int main()
{
    in.getline(A+1, maxn);
    in.getline(B+1, maxn);
    N = strlen(A+1);
    M = strlen(B+1);
    buildFunction();
    KMPmatch();
    out << k << '\n';
    int max = (k <= 1000 ? k : 1000);
    for (int i = 1; i <= max; i++) out << pos[i] << ' ';

    return 0;
}