Cod sursa(job #2288131)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 22 noiembrie 2018 21:09:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 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], v[1050], ans;
//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];
            ans++;
            if(ans<=1000)
            v[ans] = i-n;
        }
    }
    fout << ans << '\n';
    for(int i = 1; i <= min(ans, 1000); i++)
        fout << v[i] << " ";
    return 0;
}