Cod sursa(job #979559)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 1 august 2013 22:58:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 3.98 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
char a[2000005],b[2000005];
int na,nb,nv,b1,i,i1,nr,vr[1005],ax,pos,k;
struct vectorptetc
{
    char ch;
    int val,hyp;
} v[2000005];
int main(void)
{
    FILE * f;
    f=fopen("strmatch.in","r");
    ofstream g("strmatch.out");
    fgets(a,2000002,f);
    fgets(b,2000002,f);
    na=strlen(a);
    na--;
    nv=0;
    v[nv].ch=' ';
    v[nv].val=v[nv].hyp=0;
    for (i=0;i<na;i++)
    {
        nv++;
        v[nv].ch=a[i];
        v[nv].hyp=0;
        v[nv].val++;
    }
    for (i=2;i<=nv;i++)
        {
            if ((v[1].ch==v[i].ch)&&(v[1].val==v[i].val))
            {
                b1=0;
                for (i1=i;i1<=nv;i1++)
                    if ((v[i1].ch!=v[1+i1-i].ch)||(v[i1].val!=v[1+i1-i].val))
                    {
                        if ((v[i1].ch==v[1+i1-i].ch)&&(v[i1].val<v[1+i1-i].val)&&(v[i1].hyp==0))
                            v[i1].hyp=1+i1-i;
                        i=i1;
                        i1=nv+1;
                        b1=1;
                    }
                    else
                        if (v[i1].hyp==0)
                            v[i1].hyp=1+i1-i;
            }
            else
                if ((v[1].ch==v[i].ch)&&(v[1].val>v[i].val))
                            v[i].hyp=1;
        }
    nb--;
    ax=0;
    while (b[ax]!=v[1].ch)
        ax++;
    pos=1;
    k=0;
    nb=strlen(b)-1;
    for (i=ax;i<nb;i++)
    {
        if (b[i]==v[pos].ch)
        {
            k++;
            if (v[pos].val==k)
            {
                pos++;
                k=0;
            }
        }
        else
        {
            if (k==0)
            {
                pos--;
                k=v[pos].val;
            }
            b1=0;
            while ((pos!=0)&&(b1==0))
                {
                    pos=v[pos].hyp;
                    if (((b[i]==v[pos].ch)&&(v[pos].val>k))||((v[pos].val==k)&&(b[i]==v[pos+1].ch)))
                    {
                        if (v[pos].val==k)
                        {
                            pos++;
                            k=0;
                        }
                        b1=1;
                        k++;
                        if (v[pos].val==k)
                        {
                            pos++;
                            k=0;
                        }
                    }
                }
            if (pos==0)
            {
                pos=1;
                k=0;
                while ((i<nb)&&(b[i]!=v[1].ch))
                    i++;
                if (i<nb)
                    {
                        k++;
                        if (v[pos].val==k)
                        {
                            pos++;
                            k=0;
                        }
                    }
            }
        }
        if (pos==nv+1)
        {
            nr++;
            if (nr<=1000)
                vr[nr]=i-na+1;
            k=v[nv].val;
            pos--;
            if (pos==1)
                k--;
            else
            {
                pos=v[pos].hyp;
                if (pos==0)
                {
                    pos=1;
                    k=0;
                    while ((i<nb)&&(b[i]!=v[1].ch))
                        i++;
                    if (i<nb)
                        {
                            k++;
                            if (v[pos].val==k)
                            {
                                pos++;
                                k=0;
                            }
                        }
                }
                else
                    if (k==v[pos].val)
                    {
                        k=0;
                        pos++;
                    }
            }
        }
    }
    g<<nr<<'\n';
    for (i=1;((i<=nr)&&(i<=1000));i++)
        g<<vr[i]<<' ';
    g.close();
    return 0;
}