Cod sursa(job #2392523)

Utilizator DimaTCDima Trubca DimaTC Data 30 martie 2019 09:41:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include<bits/stdc++.h>
#define N 2000005
using namespace std;

string a,b;
int d[N],n,rs,k,ans[1030];
int main() {
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin>>b>>a; n=b.size();
    for (int i=1,j=0; i<b.size(); ++i) {
        if (b[i]==b[j]) {
            d[i]=d[i-1]+1;
            ++j;
        } else {
            while (j && b[i]!=b[j]) j=d[j-1];
            if (b[i]==b[j]) d[i]=j+1, ++j;
        }
    }
    b+="+";
    for (int i=0, j=0; i<a.size(); ++i) {
        if (a[i]==b[j]) {
            ++j;
        } else {
            while (j && a[i]!=b[j]) j=d[j-1];
            if (a[i]==b[j]) ++j;
        }
        if (j==n && ++rs<=1000) ans[rs]=i-n+1;
    }
    cout<<rs<<'\n';
    for (int i=1; i<=min(rs,1000); ++i) cout<<ans[i]<<" ";
    return 0;
}