Cod sursa(job #1830952)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 17 decembrie 2016 11:46:53
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;
string text, patern;
int lp[2000000];
vector <int> ap;
int l;
int lpatern;
void make_patern()
{
    int j=0;
    lpatern=patern.length();
    for(int i=1;i<lpatern;i++)
    {
        if(patern[i]==patern[j])
        {
            lp[i]=j+1;
            j++;
        }
        else
        {
            j--;
            while(j>=0)
            {
                j=lp[j];
                if(patern[i]==patern[j])
                {
                    lp[i]=j+1;
                    j++;
                    break;
                }
                else
                    j--;
            }
            if(j<0)
                lp[i]=0,j=0;
        }
    }
}
void rezolvare()
{
    int j=0;
    int lim=text.length();
    for(int i=0;i<lim;i++)
    {
        //cout<<text[i]<<" "<<patern[j]<<j<<"\n";
        if(text[i]==patern[j])
            j++;
        else
        {
            if(j>0)
                j=lp[j-1];
        }
        if(j==lpatern)
        {
            ap.push_back(i-lpatern+1);
            j = lp[j - 1];
        }

    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    getline(cin,patern);
    //scanf("\n");
    getline(cin,text);
    make_patern();
    rezolvare();
    printf("%d\n", ap.size());
    if(ap.size()<=1000)
    {
        for(int i=0;i<ap.size();i++)
            printf("%d ", ap[i]);
    }
    else
    {
        for(int i=0;i<1000;i++)
            printf("%d ", ap[i]);
    }
    return 0;
}