Cod sursa(job #2847116)

Utilizator Emmy432622Rotariu Emanuel Emmy432622 Data 10 februarie 2022 11:42:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");

string a,b;
vector<int> ans;
int p[4000005],ap;

int main()
{
    fin >> a;
    int m = a.size();
    fin >> b;
    a += '#';
    a += b;
    int n = a.size();

    p[0] = 0;

    for(int i = 1 ; i < n ; i ++)
    {
        int j = p[i-1];
        while(j && a[i]!=a[j])
            j = p[j-1];
        if(a[i]==a[j])
            j++;
        p[i]=j;

        if(p[i]==m)
        {
            ++ap;
            ans.push_back(i-2*m);
        }
    }

    fout << ap << '\n';
    for(auto it:ans)
        fout << it << ' ';

    return 0;
}