Cod sursa(job #3257998)

Utilizator mariusharabariMarius Harabari mariusharabari Data 20 noiembrie 2024 15:00:10
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int m, n, k, i, f[2000001], N, r, v[1001];
char p[2000001], t[2000001];

void prefix(){
    f[0]=-1;
    for(i=1;i<=m;i++){
        k=f[i-1];
        while(k>=0&&p[k]!=p[i-1]){
            k=f[k];
        }
        if(k==-1)
            f[i]=0;
        else
            f[i]=k+1;
    }
}

int kmp(){
    k=0;
    while(i<=n-m&&k<m){
        if(t[i+k]==p[k]) k++;
        else if(k==0) i++;
        else{
            i+=k-f[k];
            k=f[k];
        }
    }
    if(k==m) return i;
    return -1;
}
int main(){
    fin>>p;
    fin>>t;
    m=strlen(p);
    n=strlen(t);

    prefix();

    k=0;
    i=0;
    while(r!=-1){
        r=kmp();

        if(r!=-1){
            N++;
            if(N<=1000)
                v[N]=r;
        }
        i++;

    }
    fout<<N<<endl;
    for(i=1;i<=1000&&i<=N;i++) fout<<v[i]<<' ';
    return 0;
}