Cod sursa(job #3321091)

Utilizator stefan_anastasiuAnastasiu Stefan stefan_anastasiu Data 8 noiembrie 2025 10:28:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

char s[2000005], t[2000005];
int lps[2000005], rez[2000005],i,nr;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

void ps(char s[]){
     int m=strlen(s);
     int lg=0, i=1;
     while(i<m){
        if(s[lg]==s[i]){
            lg++;
            lps[i]=lg;
            i++;
        }
        else if (lg)lg=lps[lg-1];
        else
        {lps[i]=0;
        i++;}
     }
}

void kmp (char t[], char s[]){
     int n=strlen(t);
     int m=strlen(s);
     ps(s);
     int lg=0, i=0;
     while(i<n){
        if(t[i]==s[lg]){
            lg++;
            i++;
            if(lg==m){
            rez[++nr]=i-lg;
            lg=lps[lg-1];
            }
        }
        else if(lg)lg=lps[lg-1];
        else i++;
     }
}

int main()
{
    f>>s>>t;
    kmp(t, s);
    g<<nr<<'\n';
    for(i=1;i<=nr;i++)g<<rez[i]<<" ";
    return 0;
}