Cod sursa(job #721571)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 23 martie 2012 20:05:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
vector<int>p;
char a[2000002],b[2000002];
int u[2000002],n,m,sol=0;

void prefix(){
    int i,k=-1;
    u[0]=-1;
    for(i=1;i<n;i++){
        while(k>-1&&a[i]!=a[k+1])k=u[k];
        if(a[i]==a[k+1])k++;
        u[i]=k; }
}

void kmp(){
    int i,k=-1;
    for(i=0;i<m;i++){
        while(k>-1&&b[i]!=a[k+1])k=u[k];
        if(b[i]==a[k+1])k++;
        if(k==n-1){ sol++; p.push_back(i-k); k=u[k]; } }
}

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
        scanf("%s ",a);
        scanf("%s ",b);
    n=strlen(a);
    m=strlen(b);
    prefix();
    kmp();
    printf("%d\n",sol);
    for(int i=0;i<p.size();i++)printf("%d ",p[i]);
}