Cod sursa(job #2719111)

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

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

    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin.getline(s, 101);
    m=strlen(s);
    fin.getline(sm, 101);
    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;

}