Cod sursa(job #2217278)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 29 iunie 2018 20:39:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

const int DIM = 2000001;
char text[DIM], pattern[DIM];
int T, P;
int prefix[DIM], ap[1001], nrap;

void calcul_prefix(char *S, int N)
{
    int q = 0;
    prefix[1] = 0;
    for(int i = 2; i <= N; i++)
    {
        while(q > 0 && S[q] != S[i - 1])
            q = prefix[q];
        if(S[q] == S[i - 1])
            q++;
        prefix[i] = q;
    }
}
void KMP(char *text, int T, char *pattern, int P)
{
    int q = 0;
    for(int i = 1; i <= T; i++)
    {
        while(q > 0 && pattern[q] != text[i - 1])
            q = prefix[q];
        if(pattern[q] == text[i - 1])
            q++;
        if(q == P && nrap < 1000)
            ap[++nrap] = i - P;
    }
}
int main()
{
    in.getline(pattern, DIM);
    P = in.gcount() - 1;
    in.getline(text, DIM);
    T = in.gcount() - 1;
    calcul_prefix(pattern, P);
    KMP(text, T, pattern, P);
    out << nrap << '\n';
    for(int i = 1; i <= nrap; i++)
        out << ap[i] << ' ';
    return 0;
}