Pagini recente » Rating Borsos Tamas (btamasya) | Cod sursa (job #2508345) | Cod sursa (job #598872) | Cod sursa (job #2677542) | Cod sursa (job #1614571)
#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[NMax], 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) {
if (nm < 1000)
matches[++nm] = i - len1 + 1;
else
++nm;
}
}
g << nm << "\n";
for (int i = 1; i <= nm && i <= 1000; i++)
g << matches[i] - 1 << " ";
return 0;
}