Cod sursa(job #2734664)

Utilizator Mihai7218Bratu Mihai-Alexandru Mihai7218 Data 1 aprilie 2021 11:06:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001], b[2000001];
int pi[50001], i, cnt;
queue<int> Q;
void kmp()
{
    int k = 0;
    pi[1] = 0;
    for (i = 2; i < strlen(a); i++)
    {
        while(k>0 && a[k+1] != a[i])
            k = pi[k];
        if (a[k+1] == a[i])
            k++;
        pi[i] = k;
    }
    int q = 0;
    for (i = 1; i < strlen(b); i++)
    {
        while (q > 0 && a[q+1]!= b[i])
            q = pi[q];
        if (a[q+1] == b[i])
            q++;
        if (q == strlen(a)-1)
        {
            Q.push(i-strlen(a)+1);
            cnt++;
        }
        if (cnt >= 1000) return;
    }
}
int main()
{
    fin >> a+1 >> b+1;
    a[0] = ' ';
    b[0] = ' ';
    kmp();
    fout << cnt << "\n";
    while (! Q.empty())
    {
        fout << Q.front() << " ";
        Q.pop();
    }
    return 0;
}