Cod sursa(job #3256306)

Utilizator Dragos__1_1Dragos Antohi Dragos__1_1 Data 14 noiembrie 2024 08:45:18
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,M,N,i,j,q;
char s[2000003],t[2000003];
int pi[2000003],pos[1003];
int main()
{
    f>>s;
    M=strlen(s);
    for (i=M;i>0;i--){
        s[i]=s[i-1];
    }
    f>>t;
    N=strlen(t);
    for (i=N;i>0;i--){
        t[i]=t[i-1];
    }
    //cout<<M<<' '<<N<<' '<<(s+1)<<' '<<(t+1);
        for (i=2;i<=M;i++){
        while(q&&s[i]!=s[q+1])
            q=pi[q];
        if (s[i]==s[q+1])q++;
        pi[i]=q;
    }
    for (i=1;i<=N;i++){
        while (q&&s[q+1]!=t[i])
            q=pi[q];
        if (s[q+1]==t[i])
            q++;
        if (q==M){
            n++;
            q=pi[M];
            if (n<=1000){
                pos[n]=i-M;
            }
        }
    }
    g<<n<<'\n';
    for (i=1;i<=n;i++){
        g<<pos[i]<<' ';
    }
    return 0;
}