Cod sursa(job #2910594)

Utilizator answarIonascu Andrei answar Data 22 iunie 2022 16:44:58
Problema Potrivirea sirurilor Scor 52
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,i,subsecv,l;
int w[2000010],rez[1010];
char a[2000010],b[2000010];
int main() {
    fin>>a+1;
    fin>>b+1;
    n=strlen(a+1);
    m=strlen(b+1);
    l=0;
    w[1]=0;
    for (i=2;i<=n;i++) {
        while (a[i]!=a[l+1]&&l!=0) {
            l=w[l];
        }
        if (a[i]==a[l+1]) {
            l++;
        }
        w[i]=l;
    }

    for (i=1;i<=m;i++) {
        while (b[i]!=a[l+1]&&l!=0) {
            l=w[l];
        }
        if (b[i]==a[l+1]) {
            l++;
        }
        if (l==n) {
            subsecv++;
            if (subsecv<=1000) {
                rez[subsecv]=i-n;
            }
            l=w[l];
        }
    }
    fout<<subsecv<<"\n";
    for (i=1;i<=min(subsecv,1000);i++) {
        fout<<rez[i]<<" ";
    }
    return 0;
}