Pagini recente » Cod sursa (job #32073) | Cod sursa (job #1976672) | Cod sursa (job #1692521) | Cod sursa (job #2168007) | Cod sursa (job #1614556)
#include <fstream>
#include <string.h>
#define NMax 2000010
#define BASE 73
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int len1, len2, matches[1010], nm;
unsigned long long H[NMax], powB[NMax];
char str1[NMax], str2[NMax];
unsigned long long getHash(int start, int finish)
{
return (H[finish] - H[start - 1] * powB[finish - start + 1]);
}
int main()
{
f.getline(str1 + 1, 2000001);
f.getline(str2 + 1, 2000001);
len1 = strlen(str1 + 1);
len2 = strlen(str2 + 1);
powB[0] = 1;
for (int i = 1; i <= len2; i++)
powB[i] = powB[i - 1] * BASE;
unsigned long long hashMatch = 0;
for (int i = 1; i <= len1; i++)
hashMatch = hashMatch * BASE + str1[i];
for (int i = 1; i <= len2; i++)
H[i] = H[i - 1] * BASE + str2[i];
for (int i = len1; i <= len2; i++) {
if (getHash(i - len1 + 1, i) == hashMatch) {
matches[++nm] = i - len1 + 1;;
if (nm == 1000) {
nm = 1000;
break;
}
}
}
g << nm << "\n";
for (int i = 1; i <= nm; i++)
g << matches[i] - 1 << " ";
return 0;
}