Cod sursa(job #2190926)

Utilizator danielsociuSociu Daniel danielsociu Data 1 aprilie 2018 00:37:18
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#define MAX 2000050
int urmator[MAX],N,M,K=0,SOL[MAX];
char s[MAX], cuv[MAX];

void read(){
    cin>>cuv;
    cin>>s;
    N=strlen(s);
    M=strlen(cuv);
}

void initurm(){
    int i,j;
    urmator[0]=-1;
    j=-1;
    for(int i=0;i<M;i++,j++,urmator[i]=j)
        while(j>=0&&cuv[i]!=cuv[j])
            j=urmator[j];
}

void KMP(int i, int j){
    initurm();
    for(i,j=0;i<N&&j<M;i++,j++){
        while(j>=0&&s[i]!=cuv[j])
            j=urmator[j];
        if(j==M-1){
            SOL[++K]=i-j;
            KMP(i-j+1,0);
            }

        }

}
void write(){
    cout<<K<<'\n';
    if(K>1000)
        for(int i=1;i<=1000;i++)
            cout<<SOL[i]<<" ";
    else
        for(int i=1;i<=K;i++)
            cout<<SOL[i]<<" ";

}
int main(){
    read();
    KMP(0,0);
    write();
    return 0;
}