Cod sursa(job #2853741)

Utilizator elenacurecheriuElena Curecheriu elenacurecheriu Data 20 februarie 2022 16:21:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int N = 4e6;
string a, b, s;
long long a_len, b_len, s_len;
long long kmp[N+5], ans[1005];
long long k, cnt;

int main()
{
    fin>>a>>b;
    s='$'+a+'$'+b;
    a_len=a.size();
    b_len=b.size();
    s_len=s.size();
    if(a_len>b_len)
    {
        fout<<0;
        return 0;
    }
    for(int i=2; i<s_len; i++)
    {
        while (k!=0 && s[i]!=s[k+1])
            k=kmp[k];
        if (s[i]==s[k+1])
            k++;
        kmp[i]=k;
        if(a_len == kmp[i])
        {
            cnt++;
            if(cnt<=1000)
                ans[cnt]=i-1-2*a_len;
        }
    }
    fout<<cnt<<'\n';
    cnt=min(cnt, 1LL*1000);
    for(int i=1; i<=cnt; i++)
        fout<<ans[i]<<" ";
    return 0;
}