Cod sursa(job #2716557)

Utilizator pielevladutPiele Vladut Stefan pielevladut Data 5 martie 2021 12:29:39
Problema Potrivirea sirurilor Scor 100
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[2000005];
char b[2000005];
int pi[2000005];
vector<int> sol;

int main()
{
    fin >> (a+1) >> (b+1);
    int n = strlen(a+1);
    int m = strlen(b+1);
    int j = 0;
    for(int i = 2; i <= n; i ++)
    {
        while(j > 0 && a[i] != a[j+1])
        {
            j = pi[j];
        }
        if(a[i] == a[j + 1])
            j++;
        pi[i] = j;
    }
    j = 0;
    int ans = 0;
    for(int i = 1; i <= m; i ++)
    {
        while(j > 0 && b[i] != a[j + 1])
        {
            j = pi[j];
        }
        if(b[i] == a[j + 1])
            j++;
        if(j == n)
        {
            sol.push_back(i - n);
        }
    }
    ans = sol.size();
    fout << ans << '\n';
    ans = min(ans,1000);
    for(int i = 0; i < ans; i ++)
        fout << sol[i] << ' ';
    return 0;
}