Cod sursa(job #2009142)

Utilizator tavonSuleyman Magnificul tavon Data 8 august 2017 17:29:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb

#include <bits/stdc++.h>

using namespace std;

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

const int kMaxN = 2000001;
string A,B;
int pi[kMaxN];
int sol[1002];
int ans;

int main(){
    
    in>>A>>B;
    
    unsigned w = 0;
    
    for(unsigned i=1; i<A.size(); i++) {
        while(w && A[i] != A[w]) w=pi[w-1];
        if(A[i] == A[w]) w++;
        pi[i] = w;
    }

    w = 0;
    
    for(unsigned i=0; i<B.size(); i++) {
        while(w && B[i] != A[w]) w=pi[w-1];
        if(B[i] == A[w]) w++;
        if(w==A.size()){
            ans++;
            sol[min(ans,1001)] = i-A.size()+1;
        }
    }
    
    out<<ans<<'\n';
    for(int i=1;i<=min(1000,ans);i++) out<<sol[i]<<' ';
    
    return 0;
}