Cod sursa(job #2467540)

Utilizator TheNextGenerationAyy LMAO TheNextGeneration Data 4 octombrie 2019 16:41:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N = 2e6+5;
int pi[N],sol[1005];
char a[N],b[N];
int n,m;
void PiTable()
{
    int q = 0;
    pi[1] = 0;
    for (int i = 2; i<=n; i++)
    {
        while (a[i]!=a[q+1] && q>0)
            q = pi[q];
        if (a[i] == a[q+1])
            q++;
        pi[i] = q;
    }
}
int main()
{
    in >> (a+1) >> (b+1);
    n = strlen(a+1); m = strlen(b+1);
    PiTable();
    int q = 0, ans = 0;
    for (int i = 1; i<=m; i++)
    {
        while (b[i]!=a[q+1] && q>0)
            q = pi[q];
        if (b[i] == a[q+1])
            q++;
        if (q == n)
        {
            ans++;
            if (ans<=1000)
                sol[ans] = i-n;
        }
    }
    out << ans << "\n";
    for (int i = 1; i<=min(ans,1000); i++)
        out << sol[i] << " ";
}