Cod sursa(job #763407)

Utilizator test666013Testez test666013 Data 2 iulie 2012 10:40:04
Problema Potrivirea sirurilor Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define MAX 2000002

int n,m,u[MAX],s[1002],nr;
char a[MAX],b[MAX];

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

void kmp(){
    int k,i = 0;
    while(isalpha(b[i])) i++;
    for(m=i;i>0;i--)b[i]=b[i-1];
    k = 0;
    for(int i=1;i<=m;i++)
    {
        while(k>0 && a[k+1] != b[i])k=u[k];
        if(a[k+1] == b[i])k++;
        if(k==n)
        {
            nr++;
            if(nr<=1000)s[nr]=i-k;
            k=u[k];
        }
    }
}

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
        scanf("%s ",a);
        scanf("%s ",b);
    prefix();
    kmp();

    printf("%d\n",nr);
    for(int i=1;i<=min(1000,nr);i++)printf("%d ",s[i]);
    return 0;
}