Pagini recente » Cod sursa (job #1668683) | Cod sursa (job #2152748) | Cod sursa (job #482542) | Cod sursa (job #2400020) | Cod sursa (job #309450)
Cod sursa(job #309450)
#include <fstream.h>
#include <string.h>
#define MaxN 2000005
#define MaxSol 1024
char A[MaxN],B[MaxN];
long n,m,pi[MaxN],nrsol,sol[MaxSol];
void cit()
{
ifstream fin("strmatch.in");
fin.get(A,MaxN,'\n');
fin.get();
fin.get(B,MaxN,'\n');
fin.close();
m=strlen(A);
n=strlen(B);
}
void trans()
{
int i;
for(i=m;i>=1;i--)
A[i]=A[i-1];
A[0]=' ';
for(i=n;i>=1;i--)
B[i]=B[i-1];
B[0]=' ';
}
void prefix()
{
int k=0,i;
for(i=2;i<=m;i++)
{
while(k>0 && A[k+1]!=A[i])
k=pi[k];
if(A[k+1]==A[i])
k++;
pi[i]=k;
}
}
void potrivire()
{
int k=0,i;
for(i=1;i<=n;i++)
{
while(k && A[k+1]!=B[i])
k=pi[k];
if(A[k+1]==B[i])
k++;
if(k==m)
{
k=pi[m];
nrsol++;
if(nrsol<=1000)
sol[nrsol]=i-m;
}
}
}
void afis()
{
int i;
ofstream fout("strmatch.out");
fout<<nrsol<<'\n';
for(i=1;i<=nrsol;i++)
fout<<sol[i]<<" ";
fout.close();
}
int main()
{
cit();
trans();
prefix();
potrivire();
afis();
return 0;
}