Cod sursa(job #2114782)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 25 ianuarie 2018 20:59:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>
#define Nmax 2000002
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int k,n,m,p[Nmax];
char a[Nmax],b[Nmax];
vector<int> res;

int main()
{
    f>>a+1>>b+1;
    n = strlen(a+1);
    m = strlen(b+1);

    k = 0;
    for (int i=2;i<=n;i++){
        while (k!=0 && a[k+1]!=a[i]) k = p[k];
        if (a[k+1]==a[i]) k++;
        p[i] = k;
    }

    k = 0;
    for (int j=1;j<=m;j++){
        while (k!=0 && a[k+1]!=b[j]) k = p[k];
        if (a[k+1]==b[j]) k++;
        if (k==n) res.push_back(j-n);
    }

    g<<res.size()<<'\n';
    for (int i=0;i<min(1000,(int)res.size());i++) g<<res[i]<<' ';

    return 0;
}