Cod sursa(job #2217275)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 29 iunie 2018 20:34:26
Problema Potrivirea sirurilor Scor 14
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[DIM], nrap;

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