Cod sursa(job #2719127)

Utilizator Arsene_DenisaArsene Denisa Arsene_Denisa Data 9 martie 2021 16:45:30
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include<fstream>
#include<cstring>

using namespace std;
char s[200001], sm[2000001];
int pi[200001], r[1001];
int main() {
    int m, k, i, n, ans;

    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin.getline(s, 200001);
    m=strlen(s);
    fin.getline(sm, 200001);
    n=strlen(sm);

    for(i=m;i>=1;i--) {
        s[i]=s[i-1];
    }
     for(i=n;i>=1;i--) {
        sm[i]=sm[i-1];
    }
    k=0;
    pi[1]=0;
    for(i=2;i<=m;i++) {
        while(k>0 && s[k+1]!=s[i]) {
            k=pi[k];
        }
        if(s[k+1]==s[i]) {
            k++;
        }
        pi[i]=k;
    }

    int q=0;
    for(i=1;i<=n;i++) {
        while(q>0 && s[q+1]!=sm[i]) {
                q=pi[q];
        }
        if(s[q+1]==sm[i]) {
            q++;
        }
        if(q==m) {
                if(ans<1000){
                ans++;
        r[ans]=i-m+1;
                }
                else {
                    break;
                }
        }
        }
        fout<<ans<<"\n";
        for(i=1;i<=ans;i++) {
            fout<<r[i]-1<<" ";
        }
    return 0;

}