Cod sursa(job #3349060)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 25 martie 2026 11:11:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <cstring>
#include <vector>
#define nmax (int)(2e6+1)
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int lps[nmax];
string a,b;
vector<int>v;
void get_lps(string s){
    int i=1,len=0;
    while(s[i]!=0){
        if(s[i]==s[len])
            lps[i++]=++len;
        else if(len!=0)
            len=lps[len-1];
        else
            i++;
    }
}
int kmp(){
    int r=0,i=0,n=a.size();
    for(int j=0;b[j]!=0;j++)
        if(a[i]==b[j]){
            i++;
            if(i==n){
                r++;
                if(r<=1000)
                    v.push_back(j-n+1);
                i=lps[i-1];
            }
        }else if(i!=0)
            i=lps[i-1],j--;
    return r;
}
signed main()
{
    cin>>a>>b;
    get_lps(a);
    cout<<kmp()<<'\n';
    for(auto i:v)
        cout<<i<<" ";
    return 0;
}