Cod sursa(job #1741612)

Utilizator Y0da1NUME JMECHER Y0da1 Data 14 august 2016 14:57:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <iostream>
#include <string.h>
#include <fstream>
char w[2000002];
char s[2000002];
int match [2000002], sl, wl, potriviri[1002];

using namespace std;
void kmp_match()
{
    match [0]=0;
    int j = 0;
    for (int i = 1; i < wl; i++)
        {
        while (j > 0 && (w[j] != w[i]))
            j = match[j-1];

        if (w[j] == w[i])
            j++;
        match[i] = j;
    }
}
int main ()
{
    int nr, i=0, m=0, j=0, x=0;
    ifstream input ("strmatch.in");
    ofstream output ("strmatch.out");

    input>>w;
    input>>s;

    wl=strlen (w);
    sl=strlen (s);

    kmp_match();    ///calculam tabela


    //for(i=0;i<=wl;++i)
     //   cout<<w[i]<<" ";
    //cout<<endl;
    //for(i=0;i<wl;++i)
    //    cout<<match[i]<<" ";
    //cout<<endl;
    ///cautam propriu zis
    while (m+i<sl)
    {
        if(w[i]==s[m+i])
        {
            if(i==wl-1)
            {
                ++x;
                if(j<1000)
                {
                potriviri[j]=m;
                ++j;
                }
            }
            ++i;
        }
        else
        {
            if(i!=0)    ///nu cautam primu caracter ca ala nici n-are pref/suf
            {
                m+=i - match[i-1];
                i=match[i-1];
            }
            else
            {
                ++m;
            }
        }

    }
    /// asta nu mere da-l undeva
    /*for (i=0;i<sl;++i)
    {
        cout<<x<<" ";
        while (x>0 && w[x+1]!=s[i])
            x=match[x];
        if(w[x+1]==s[i]) ++x; ///avem o potrivire
        if(x==wl-1)
        {
            if(j<1000)
            {
                potriviri[j]=i-wl+1;
                ++j;
            }
            x=match[x];
        }
    }*/
    output<<x<<"\n";
    for (i=0;i<j;++i)
        output<<potriviri[i]<<" ";

return 0;
}