Pagini recente » Cod sursa (job #225842) | Cod sursa (job #1103968) | Cod sursa (job #866918) | Cod sursa (job #3227214) | Cod sursa (job #2807639)
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
long long i, j, k, l, m, p, x, n, hashA1, hashA2, hashB1, hashB2, P1, P2, cnt, Map[125],Caca[20000005];
#define MOD1 100007
#define MOD2 100013
#define P 73
char A[20000005], B[20000005];
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> A;
cin >> B;
int nA=strlen(A);
int nB=strlen(B);
P1 = P2 = 1;
for (i = 97, j = 0;i <= 122;i++, j++)
{
char ch = (char)(i);
Map[i] = j;
}
for (i = 65;i <= 90;i++, j++)
{
char ch = (char)(i);
Map[i] = j;
}
for (i = 48;i <= 57;i++, j++)
{
char ch = (char)(i);
Map[i] = j;
}
for (i = 0;i < nA;i++)
{
hashA1 = (hashA1 * P + Map[int(A[i])]) % MOD1;
hashA2 = (hashA2 * P + Map[int(A[i])]) % MOD2;
if (i) {
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
}
for (i = 0;i < nA;i++)
{
hashB1 = (hashB1 * P + Map[int(B[i])]) % MOD1;
hashB2 = (hashB2 * P + Map[int(B[i])]) % MOD2;
}
if (hashA1 == hashB1 and hashA2 == hashB2)
Caca[cnt++]=0;
for (i = nA;i < nB;i++)
{
hashB1 = ((hashB1 - (Map[int(B[i - nA])] * P1) % MOD1 + MOD1) * P + Map[int(B[i])]) % MOD1;
hashB2 = ((hashB2 - (Map[int(B[i - nA])] * P2) % MOD2 + MOD2) * P + Map[int(B[i])]) % MOD2;
if (hashA1 == hashB1 and hashA2 == hashB2)
Caca[cnt++]=i-nA+1;
}
cout << cnt<<'\n';
if(cnt>1000) cnt=1000;
for (int i = 0;i < cnt;i++)
cout << Caca[i]<<" ";
}