Cod sursa(job #920376)

Utilizator tudy23Coder Coder tudy23 Data 20 martie 2013 11:46:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N=2000100;
char sub[N],str[N];
int pi[N];
int d[2];
vector <int> potriv;
void prefix()
{
    int k=0;
    pi[1]=0;
    for(int i=2;i<=d[0];++i)
    {
        while(k>0&&sub[k+1]!=sub[i])
            k=pi[k];
        if(sub[k+1]==sub[i])
            ++k;
        pi[i]=k;
    }
}
void kmp()
{
    prefix();
    int k=0;
    for(int i=1;i<=d[1];++i)
    {
        while(k>0&&sub[k+1]!=str[i])
            k=pi[k];
        if(sub[k+1]==str[i])
            ++k;
        if(k==d[0])
            potriv.push_back(i-d[0]);
        if(potriv.size()==1000)
            return;
    }
}
void citire()
{
    freopen("strmatch.in","r",stdin);
    gets(sub+1);
    d[0]=strlen(sub+1);
    gets(str+1);
    d[1]=strlen(str+1);
}
void afisare()
{
    freopen("strmatch.out","w",stdout);
    printf("%d\n",potriv.size());
    for(int i=0;i<potriv.size();++i)
        printf("%d ",potriv[i]);
}
int main()
{
    citire();
    kmp();
    afisare();
    return 0;
}