Cod sursa(job #1991810)

Utilizator mircearoataMircea Roata Palade mircearoata Data 18 iunie 2017 14:04:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

string problema = "strmatch";

ifstream in(problema+".in");
ofstream out(problema+".out");

int a,b,cnt,v[2000001];
char A[2000001],B[2000001];

int T[2000001];

void kmp_table()
{
    int pos=1,cnd=0;
    T[0]=-1;
    while(pos<a)
    {
        if(A[pos]==A[cnd])
        {
            T[pos]=T[cnd];
            pos++;cnd++;
        }
        else
        {
            T[pos]=cnd;
            cnd=T[cnd];
            while(cnd>=0 && A[pos]!=A[cnd])
            {
                cnd=T[cnd];
            }
            pos++;
            cnd++;
        }
    }
    T[pos]=cnd;
}

void kmp_search()
{
    int m=0,i=0;
    while(m+i<b)
    {
        if(A[i]==B[m+i])
        {
            i++;
            if(i==a)
            {
                v[cnt++]=m;
                m=m+i-T[i];
                i=T[i];
            }
        }
        else
        {
            if(T[i]>-1)
            {
                m=m+i-T[i];
                i=T[i];
            }
            else
            {
                m=m+i+1;
                i=0;
            }
        }
    }
}

int main()
{
    in>>A>>B;
    a=strlen(A);
    b=strlen(B);
    kmp_table();
    kmp_search();
    out<<cnt<<'\n';
    for(int i = 0;i<min(cnt,1000);i++)
    {
        out<<v[i]<<' ';
    }
    return 0;
}