Cod sursa(job #221142)

Utilizator EdeNNu Cred EdeN Data 14 noiembrie 2008 20:00:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <iostream>
#include <string>
#define nmax 2000005
using namespace std;

string w,s;
int lim,pos,i,j,t[nmax],sol[1002];

void citire()
{
    char c;
    freopen("strmatch.in","r",stdin);
    c=getc(stdin);
    while (c!='\n')
        {
            w+=c;
            c=getc(stdin);
        }
    c=getc(stdin);
    while (c!='\n')
        {
            s+=c;
            c=getc(stdin);
        }
    fclose(stdin);
}

void create_table()
{
    int pos=2;
    int cnd=0;
    t[0]=-1;
    t[1]=0;
    while (pos<s.length())
        {
            if (w[pos-1]==w[cnd])
                {
                    t[pos]=cnd+1;
                    pos++;
                    cnd++;
                }
            else
                if (cnd>0) cnd=t[cnd];
                else
                    {
                        t[pos]=0;
                        pos++;
                    }
        }
}

void search_it()
{
    int j=0,m=0,i=0;
    while (m+i<s.length())
    {
        if (w[i] == s[m+i])
        {
        i++;
        if (i==w.length())
        {
            if (j<1000)
                {
                    sol[j]=m;
                    j++;
                }
           m++;
           i=0;
        }
        }
        else
        {
            m=m+i-t[i];
            if (i>0) i=t[i];
        }
    }
    lim=j;
}
int main()
{
    citire();
    create_table();
    for (i=0; i<w.length(); i++)
        cout << t[i]<<' ';
    cout<<endl<<w<<' '<<s;
    freopen("strmatch.out","w",stdout);
    search_it();
    cout<<lim<<endl;
    for (i=0;i<lim;i++)
        cout<<sol[i]<<' ';
    return 0;
}