Cod sursa(job #1868917)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 5 februarie 2017 14:04:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int DIM = 2000001;
char A[DIM], B[DIM];
int N, M, match[DIM], nr = 0;
void prefix(int pi[])
{
    int k = 0;
    pi[1] = 0;
    for(int i = 2; i <= N; i++)
    {
        while(k > 0 && A[k] != A[i - 1])
            k = pi[k];
        if(A[k] == A[i - 1])
            k++;
        pi[i] = k;
    }
}
int KMP(char *A, char *B)
{

    int pi[N], q = 0;
    prefix(pi);
    for(int i = 1; i <= M; i++)
    {
        while(q > 0 && A[q] != B[i - 1])
            q = pi[q];
        if(A[q] == B[i - 1])
            q++;
        if(q == N)
            match[++nr] = i - N;
    }
    return nr;
}
int main()
{
    f.getline(A, DIM);
    N = f.gcount() - 1;
    f.getline(B, DIM);
    M = f.gcount() - 1;
    int ap = KMP(A, B);
    g << ap << '\n';
    for(int i = 1; i <= ap && i <= 1000; i++)
        g << match[i] << ' ';
    return 0;
}