Cod sursa(job #2833838)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 15 ianuarie 2022 19:24:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.57 kb
#include <bits/stdc++.h>
using namespace std;
ofstream fout("strmatch.out");
int sol,len,kmp[4000050];string a,b;
int main (){
ifstream("strmatch.in")>>b>>a, a=' '+b+'$'+a;
kmp[0]=-1;
for(int i=1; i<(int)a.size(); i++){
    len=kmp[i-1];
    while(a[len+1]!=a[i]&&len >= 0)
        len=kmp[len];
    kmp[i]=len+1;
}
queue<int>start;
for(int i=1; i < a.size(); i++)
    if(kmp[i] == b.size())
        if(++sol <= 1000)
            start.push(i-1-2*b.size());
fout<<sol<<'\n';
while(!start.empty()){
    fout<<start.front()<<' ';
    start.pop();
}
return 0;
}