Cod sursa(job #3330337)

Utilizator vladneaguVladneagu vladneagu Data 18 decembrie 2025 19:11:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include <queue>
using namespace std;
const int maxn=4e6+5;
int kmp[maxn];
signed main() {
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string a,b;
    cin>>a>>b;
    string s=a+"#"+b;
    kmp[0]=0;
    int cnt=0;
    for(int i=1;i<s.length();i++) {
        kmp[i]=0;
        int x=kmp[i-1];
        while (x && s[x]!=s[i])x=kmp[x-1];
        if (s[x] == s[i])x++;
        kmp[i]=x;
        cnt+=(x==a.size());
    }
    cout<<cnt<<endl;
    int cnt2=0;
    for(int i=1;i<s.length();i++) {
        if (kmp[i]==a.size()) {
            cnt2++;
            if (cnt2==1001)break;
            cout<<i-a.size()-3<<" ";
        }
    }
    return 0;
}