Cod sursa(job #2498569)

Utilizator andreistanStan Andrei andreistan Data 24 noiembrie 2019 01:36:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

const int NMAX = 2000001;
int lgT, lgP, n;
char T[NMAX], P[NMAX];
int pi[NMAX], pos[1001];

void prefix()
{
    int k = 0;
    pi[0] = 0;
    int i = 1;
    while(i < lgP)
        if(P[i] == P[k])
        {
            k++;
            pi[i] = k;
            i++;
        }
        else if(k != 0)
            k = pi[k - 1];
        else
        {
            pi[i] = 0;
            i++;
        }
}



void kmp()
{
    /// cu i ne deplasam in text
    /// cu j ne deplasam in patern
    int i = 0;
    int j = 0;
    prefix();
    while(i < lgT)
    {
        if(T[i] == P[j])
        {
            i++;
            j++;
        }
        if(j == lgP)
        {
            /// avem solutie
            n++;
            pos[n] = i - j;
            j = pi[j - 1];
        }
        else if(i < lgT && T[i] != P[j])
            if(j)
                j = pi[j - 1];
            else
                i++;
    }
}
int main()
{
    f.getline(P, NMAX);
    lgP = f.gcount() - 1;
    f.getline(T, NMAX);
    lgT = f.gcount() - 1;
    kmp();
    g << n << '\n';
    int minn = min(1000, n);
    for(int i = 1; i <= minn; i++)
        g << pos[i] << ' ';
    return 0;
}