Cod sursa(job #3348401)

Utilizator altomMirel Fanel altom Data 21 martie 2026 15:21:47
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX=4e6+5;
string a, b, s;
int kmp[NMAX];

int main()
{
    fin>>a>>b;

    s=a+b;

//    cout<<s<<'\n';
    kmp[0]=0;
    int cnt=0;
    for(int i=1;i<s.size();i++){
        int j=kmp[i-1];
        while(s[i]!=s[j] && j!=0){
            j=kmp[j-1];
        }
        kmp[i]=j;
        if(s[i]==s[j])
            kmp[i]++;

        if(kmp[i]==a.size()){
            cnt++;
        }
    }

    fout<<cnt<<'\n';

    for(int i=0;i<s.size();i++){
        if(kmp[i]==a.size()){
            fout<<i-2*int(a.size())+1<<" ";
        }
    }


    return 0;
}