Pagini recente » Cod sursa (job #1456369) | Cod sursa (job #2358834) | Cod sursa (job #1911404) | Cod sursa (job #2744758) | Cod sursa (job #2678293)
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
# define D 73
# define MOD1 100007
# define MOD2 100021
# define MAXN 2000001
char S[MAXN], P[MAXN];
int lS, lP;
int hashP1, hashP2, d1, d2;
char match[MAXN];
int main()
{
fin.getline(P, MAXN);
fin.getline(S, MAXN);
lS=strlen(S);
lP=strlen(P);
d1=d2=1;
for(int i=0; i<lP; i++)
{
hashP1=(hashP1*D+P[i])%MOD1;
hashP2=(hashP2*D+P[i])%MOD2;
if(i!=0){
d1=(d1*D)%MOD1;
d2=(d2*D)%MOD2;
}
}
if(lP>lS)
{
fout<<0;
return 0;
}
int hash1=0, hash2=0;
for(int i=0; i<lP; i++)
{
hash1=(hash1*D+S[i])%MOD1;
hash2=(hash2*D+S[i])%MOD2;
}
int sol=0;
if(hash1==hashP1 && hash2==hashP2)
match[0]=1, sol++;
for(int i=lP; i<lS; i++)
{
hash1=(((hash1-S[i-lP]*d1)%MOD1+MOD1)*D+S[i])%MOD1;
hash2=(((hash2-S[i-lP]*d2)%MOD2+MOD2)*D+S[i])%MOD2;
if(hash1==hashP1 && hash2==hashP2)
match[i-lP+1]=1, sol++;
}
fout<<sol<<"\n";
sol=0;
for(int i=0; i<lS && sol<10000; i++)
if(match[i])
{
sol++;
fout<<i<<" ";
}
return 0;
}