Cod sursa(job #2365721)

Utilizator Bogdy_PPrunescu Bogdan Bogdy_P Data 4 martie 2019 15:58:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char B[2000100], A[2000100];
int p[2000100], m, n;
void pref()
{
    int q = 0;
    p[1] = 0;
    for(int i = 2; i <= m;i++)
    {
        while(q && B[q + 1] != B[i])
            q = p[q];
        if(B[q + 1] == B[i])
            q++;
        p[i] = q;
    }
}
int q, k, pos[1010];
int main()
{
    in.getline(B + 1, 2000002);
    in.getline(A + 1, 2000002);
    m = strlen(B + 1);
    n = strlen(A + 1);
    pref();
    /*for(int i = 1;i <= m;i++)
        cout << p[i] << " ";*/
    for(int i = 1;i <= n;i++)
    {
        while(q && B[q + 1] != A[i])
            q = p[q];
        if(B[q + 1] == A[i])q++;
        if(q == m)
        {
            q = p[m];
            if(k + 1 <= 1000)pos[++k] = i - m;
        }
    }
    out << k << '\n';
    for(int i = 1;i <= min(k, 1000);i++)
        out << pos[i] << " ";
    return 0;
}