Cod sursa(job #1725483)

Utilizator liviu23Liviu Andrei liviu23 Data 5 iulie 2016 19:17:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <string.h>
#define DIM 2000005
using namespace std;

char a[DIM],b[DIM];
int ps[DIM],l1,l2,nP,ans[DIM];

void kmp() {
    int q=0;
    for(int i=0;i<l2;i++) {
        while(q>0&&a[q]!=b[i])
            q=ps[q-1];
        if(a[q]==b[i])
            q++;
        if(q==l1)
            ans[nP++]=i-l1+1;
    }
}

void computePS() {
    int j=0;
    for(int i=1;i<l1;i++) {
        while(j>0&&a[j]!=a[i])
            j=ps[j-1];
        if(a[j]==a[i])
            j++;
        ps[i]=j;
    }
}

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin.getline(a,DIM);
    fin.getline(b,DIM);
    l1=strlen(a);
    l2=strlen(b);
    computePS();
    kmp();
    fout<<nP<<'\n';
    for(int i=0;i<min(1000,nP);i++)
        fout<<ans[i]<<" ";
    return 0;
}