Pagini recente » Cod sursa (job #2173214) | Cod sursa (job #355301) | Cod sursa (job #1601348) | Cod sursa (job #1300749) | Cod sursa (job #1229686)
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
const char infile[] = "strmatch.in";
const char outfile[] = "strmatch.out";
ifstream fin(infile);
ofstream fout(outfile);
const int MAXN = 2000005;
const int P = 79;
const int mod1 = 100007;
const int mod2 = 100022;
char A[MAXN], B[MAXN];
int N, M, hashA1, hashA2, P1 = 1, P2 = 1, hashB1, hashB2;
vector <int> match;
int main()
{
fin >> (A + 1) >> (B + 1);
N = strlen(A + 1);
M = strlen(B + 1);
if(N > M)
{
fout << "0\n";
fin.close();
fout.close();
return 0;
}
for(int i = 1 ; i <= N ; ++ i)
{
hashA1 = (hashA1 * P + A[i]) % mod1;
hashA2 = (hashA2 * P + A[i]) % mod2;
P1 = (P1 * P) % mod1;
P2 = (P2 * P) % mod2;
}
for(int i = 1 ; i <= N ; ++ i)
{
hashB1 = (hashB1 * P + B[i]) % mod1;
hashB2 = (hashB2 * P + B[i]) % mod2;
}
for(int i = 1 ; i <= M - N + 1 ; ++ i)
{
if(hashA1 == hashB1 && hashA2 == hashB2)
match.push_back(i - 1);
hashB1 = (((((hashB1 * P) % mod1 - (B[i] * P1) % mod1 + mod1) % mod1) + B[i + N]) % mod1);
hashB2 = (((((hashB2 * P) % mod2 - (B[i] * P2) % mod2 + mod2) % mod2) + B[i + N]) % mod2);
}
fout << match.size() << endl;
for(int i = 0 ; i < match.size() ; ++ i)
fout << match[i] << ' ';
fin.close();
fout.close();
return 0;
}