Cod sursa(job #2173688)

Utilizator raulrusu99Raul Rusu raulrusu99 Data 15 martie 2018 23:36:36
Problema Potrivirea sirurilor Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define N_MAX 2000005
char P[N_MAX], T[N_MAX];
int n, m, Pi[N_MAX], k, rez;
vector <int> v;
int main()
{
    f >> P + 1;
    f >> T + 1;
    n = strlen(P + 1);
    m = strlen(T + 1);
    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;
    }

    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)
        {
            rez++;
            if(rez <= 1000)
                v.push_back(i - n);
            k = Pi[k];
        }
    }
    g << rez << "\n";
    for(int i = 0; i < v.size(); i++)
        g << v[i] << " ";
    return 0;
}