Pagini recente » Cod sursa (job #2972222) | Cod sursa (job #3003010) | Borderou de evaluare (job #20123) | Cod sursa (job #2490862) | Cod sursa (job #1984004)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int mod1 = 100007, mod2 =666013, p =79;
int sol[1007], n2, n1, p1, p2, hash1, hash2, hashv1, hashv2, nr;
char v1[2000007], v2[2000007];
int main()
{
in >> v1 >> v2;
n1 = strlen(v1);
n2 = strlen(v2);
if(n1 > n2)
{
out << "0";
return 0;
}
for(int i = 0; i < n1; ++i)
{
hashv1 = (hashv1 * p + v1[i]) % mod1;
hashv2 = (hashv2 * p + v1[i]) % mod2;
hash1 = (hash1 * p + v2[i]) % mod1;
hash2 = (hash2 * p + v2[i]) & mod2;
}
p1 = p2 = 1;
for(int i = 1; i < n1; ++i)
{
p1 = (p1 * p) % mod1;
p2 = (p2 * p) % mod2;
}
if(hash1 == hashv1 && hash2 == hashv2)
sol[++nr] = 0;
for(int i = n1; i < n2; ++i)
{
hash1 = ((hash1 - (p1 * v1[i - n1]) % mod1 + mod1) * p + v1[i]) % mod1;
hash2 = ((hash2 - (p2 * v2[i - n2]) % mod2 + mod2) * p + v1[i]) % mod2;
if(hash1 == hashv1 && hash2 == hashv2)
{
nr++;
if(nr <= 1000)
sol[nr] = i - n1 + 1;
}
}
out << nr << "\n";
if(nr > 1000)
nr = 1000;
for(int i = 1; i <= nr; ++i)
out << sol[i] << " ";
return 0;
}