Cod sursa(job #1970741)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 19 aprilie 2017 16:06:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

string F,S;
int PRE[2000005];
int ns,nf;

void ff(){
    int i=1,len=0;
    while(i<=nf){
        if(F[i]==F[len]){
            len++;
            PRE[i]=len;
            i++;
        }
        else{
            if(len!=0)
                len=PRE[len-1];
            else{
                PRE[i]=len;
                i++;
            }
        }
    }
}
int r;
vector<int> SOL;
void kmp(){
    int i=0,j=0;
    while(i<=ns){
        if(S[i]==F[j]){
            i++;
            j++;
        }
        if(j==nf){
            r++;
            if(r<=1000){
                SOL.push_back(i-j);
            }
            j=PRE[j-1];
        }
        if(i<=ns&&S[i]!=F[j]){
            if(j!=0)
                j=PRE[j-1];
            else i++;
        }
    }
}
void solve(){
    ff();
    kmp();
    out<<r<<"\n";
    for(auto x : SOL){
        out<<x<<" ";
    }
}
int main(){
    in>>F>>S;
    nf=F.size();
    ns=S.size();
    solve();
    return 0;
}