Cod sursa(job #1404956)

Utilizator cautionPopescu Teodor caution Data 28 martie 2015 18:21:59
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <cstring>
#define MAX_LEN 2000005
#define MAX_POS_STORE 1005
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[MAX_LEN], b[MAX_LEN];
long pos[MAX_POS_STORE], v[MAX_LEN], ctr, a_len, b_len;
void kmp()
{
    long k=0;
    v[0]=0;
    for(long i=2; i<=a_len; ++i)
    {
        while(k>0&&a[k+1]!=a[i])
            k=v[k];
        if(a[k+1]==a[i]) k+=1;
        v[i]=k;
    }
    k=0;
    for(long i=1; i<=b_len; ++i)
    {
        while(k>0&&a[k+1]!=b[i])
            k=v[k];
        if(a[k+1]==b[i]) k+=1;
        if(k==a_len)
        {
            ++ctr;
            pos[ctr]=i-a_len;
            k=v[k];
        }
    }
}
void print()
{
    out<<ctr<<'\n';
    for(long i=1; i<=1000&&i<=ctr; ++i)
        out<<pos[i]<<' ';
}
int main()
{
    in>>(a+1)>>(b+1);
    a_len=strlen(a+1);
    b_len=strlen(b+1);
    kmp();
    print();
    return 0;
}