Pagini recente » Cod sursa (job #1438824) | Cod sursa (job #147770) | Cod sursa (job #2204282) | Cod sursa (job #868647) | Cod sursa (job #979415)
Cod sursa(job #979415)
#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;
}