Cod sursa(job #2719128)

Utilizator Arsene_DenisaArsene Denisa Arsene_Denisa Data 9 martie 2021 16:50:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include<fstream>
#include<cstring>
#include<vector>
using namespace std;
vector<int>r;
char s[2000001], sm[2000001];
int pi[2000001];
int main() {
    int m, k, i, n, ans;

    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin.getline(s, 2000001);
    m=strlen(s);
    fin.getline(sm, 2000001);
    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;
    ans=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.push_back(i-m);
                }
                else {
                    break;
                }
        }
        }
        fout<<r.size()<<"\n";
        for(i=0;i<r.size();i++) {
            fout<<r[i]<<" ";
        }
    return 0;

}