Cod sursa(job #2288120)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 22 noiembrie 2018 21:04:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

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

char A[2000005], B[2000005];
int n, m, k, pi[2000005];
vector <int> v;
int main()
{
    fin >> A+1;
    fin >> B+1;

    n = strlen(A+1);
    m = strlen(B+1);

    k = 0;
    for(int i = 2; i <= n; i++)
    {
        while(k>0 && A[i] != A[k+1])
            k = pi[k];
        if(A[k+1] == A[i])
            k++;
        pi[i] = k;
    }
    k = 0;
    for(int i = 1 ; i <= m; i++)
    {
        while(k>0 && A[k+1] != B[i])
            k = pi[k];
        if(A[k+1] == B[i])
            k++;
        if(k == n)
        {
            k = pi[n];
            if(v.size() < 1000)
            v.push_back(i-n);
        }
    }
    fout << v.size()<<'\n';
    for(int i = 0; i < v.size() && i < 1000; i++)
        fout << v[i] << " ";
    return 0;
}