Cod sursa(job #2056577)

Utilizator raulrusu99Raul Rusu raulrusu99 Data 4 noiembrie 2017 12:24:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#define N_MAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char P[N_MAX], T[N_MAX];
int Pi[N_MAX], k, m, n;
vector <int> v;
int main()
{
    f >> (P + 1);
    f >> (T + 1);
    n = strlen(P + 1);
    m = strlen(T + 1);
    k = 0;
    for(int i = 2; i <= n; i++)
    {
        while(k > 0 && P[k + 1] != P[i])
            k = Pi[k];
        if(P[k + 1] == P[i])
            k++;
        Pi[i] = k;
    }
    k = 0;
    for(int i = 1; i <= m; i++)
    {
        while(k > 0 && P[k + 1] != T[i])
            k = Pi[k];
        if(P[k + 1] == T[i])
            k++;
        if(k == n)
        {
            v.push_back(i - k);
            k = Pi[k];
        }
    }
    n = v.size();
    g << n << "\n";
    if(v.size() > 1000 ) n = 1000;
    for(int i = 0; i < n; i++) g << v[i] << " ";
    return 0;
}