Cod sursa(job #979415)

Utilizator Daniel3717Aleca Daniel Adrian Daniel3717 Data 1 august 2013 16:21:22
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 2.89 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++)
    {
        if (a[i]!=v[nv].ch)
        {
            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;
                    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
        {
            b1=0;
            while ((pos!=0)&&(b1==0))
                {
                    pos=v[pos].hyp;
                    if (b[i]==v[pos].ch)
                    {
                        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++;
            vr[nr]=i-na+1;
            k=v[nv].val;
            pos--;
            pos=v[pos].hyp;
            if (k==v[pos].val)
            {
                k=0;
                pos++;
            }
        }
    }
    g<<nr<<'\n';
    for (i=1;i<=nr;i++)
        g<<vr[i]<<' ';
    g.close();
    return 0;
}