Pagini recente » Cod sursa (job #2903406) | Cod sursa (job #144283) | Cod sursa (job #2688119) | Cod sursa (job #938907) | Cod sursa (job #629552)
Cod sursa(job #629552)
#include<fstream>
#include<cstring>
using namespace std;
#define baza 67
#define p 1000007
char a[2000002],b[2000002];
int n,m,alfa2[1005],alfa1[2000005];
long hash1,hash2;
int B[2000005];
int nra,poz[1005];
void putere()
{
int i;
B[0]=1;
for(i=1;i<=m;i++)
B[i]=(B[i-1]*baza)%p;
}
void transformare(char sir[],int lg1,int lg2,int alfab[],long &hash)
{
int i;
for(i=lg1;i<lg2;i++)
{
hash=(hash+(alfab[i]*B[lg2-i-1]))%p;
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.getline(a,2000005);
fin.getline(b,2000005);
n=strlen(b);
m=strlen(a);
int i;
for(i=0;i<m;i++)
if(a[i]>='a'&&a[i]<='z')
alfa2[i]=a[i]-'a';
else
if(a[i]>='A'&&a[i]<='Z')
alfa2[i]=a[i]-'A'+25+1;
else
alfa2[i]=a[i]-'0'+25+25+2;
for(i=0;i<n;i++)
if(b[i]>='a'&&b[i]<='z')
alfa1[i]=b[i]-'a';
else
if(b[i]>='A'&&b[i]<='Z')
alfa1[i]=b[i]-'A'+25+1;
else
alfa1[i]=b[i]-'0'+25+25+2;
putere();
transformare(a,0,m,alfa2,hash2);
transformare(b,0,m,alfa1,hash1);
int sw=0;
i=0;
if(hash1==hash2)
{
for(i=0;i<m;i++)
if(a[i]!=b[i])
sw++;
if(sw==0)
{
nra++;
poz[0]++;
poz[poz[0]]=1;
}
}
i=1;
while(i+m-1<=n)
{
hash1=(hash1-alfa1[i-1]*B[m-1])%p;
if(hash1<0)
hash1=hash1+p;
hash1=(hash1*baza)%p;
hash1=(hash1+alfa1[i+m-1])%p;
sw=0;
if(hash1==hash2)
{
for(int j=i;j<=m;j++)
if(a[j]!=b[j])
sw++;
if(sw==0)
{
nra++;
poz[0]++;
poz[poz[0]]=i;
}
}
i=i+1;
}
if(nra<=1000)
{
fout<<nra<<'\n';
for(int j=1;j<=nra;j++)
fout<<poz[j]<<" ";
fout<<'\n';
}
return 0;
}