Pagini recente » Cod sursa (job #1065112) | Cod sursa (job #2080631) | Cod sursa (job #624938) | Cod sursa (job #2295397) | Cod sursa (job #3160433)
#include <iostream>
#include <fstream>
#include <string.h>
#define ull unsigned long long
#define P 73
#define nMax 2000001
#define mod1 100007
#define mod2 100021
char a[nMax], b[nMax];
int lngA, lngB, p1=1, p2=1, hash1, hash2, hash3, hash4, cnt, sol[nMax];
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
fin>>a>>b;
lngA=strlen(a);
lngB=strlen(b);
if(lngA>lngB){
fout<<0;
return 0;
}
for(int i=0;i<lngA; i++){
hash1=(hash1*P+a[i])%mod1;
hash2=(hash2*P+a[i])%mod2;
if (i != 0){
p1=(p1*P)%mod1;
p2=(p2*P)%mod2;
}
}
for(int i=0;i<lngA;i++){
hash3=(hash3*P+b[i])%mod1;
hash4=(hash4*P+b[i])%mod2;
}
if (hash3 == hash1 && hash4 == hash2){
sol[0]=1;
cnt++;
}
for (int i = lngA; i < lngB; i++)
{
hash3 = ((hash3 - (b[i - lngA] * p1) % mod1 + mod1) * P + b[i]) % mod1;
hash4 = ((hash4 - (b[i - lngA] * p2) % mod2 + mod2) * P + b[i]) % mod2;
if (hash3 == hash1 && hash4 == hash2){
sol[i-lngA+1]=1;
cnt++;
}
}
fout<<cnt<<"\n";
cnt = 0;
for (int i = 0; i < lngB && cnt < 1000; i++)
if (sol[i]){
cnt++;
fout<<i<<" ";
}
return 0;
}