Cod sursa(job #2961548)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 6 ianuarie 2023 17:40:16
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int Dim = 2*1e6 + 3;
int n,m,p[Dim+Dim],cnt,k;
vector<int> ans;
string N,M;


int main()
{
    cin>>N>>M;
    n = N.size();
    m = M.size();

    if(n>m)
    {
        cout<<0;
        return 0;
    }

    N += '#';
    N += M;

    p[0] = -1;
    for(int i=1;i<=n+m+1;++i)
    {
        k = p[i-1];
        while(k>=0 && N[k] != N[i-1])
            k = p[k];

        p[i] = k+1;

        if(p[i] == n)
        {
            cnt++;
            if(ans.size()<1000)
                ans.push_back(i-n-n+1);
        }
    }
    cout<<cnt<<'\n';
    for(auto i : ans)cout<<i<<' ';
    return 0;
}