Pagini recente » Cod sursa (job #2882149) | Cod sursa (job #2684816) | Cod sursa (job #1924947) | Cod sursa (job #2858927) | Cod sursa (job #912636)
Cod sursa(job #912636)
#include <cctype>
#include <cstring>
#define DM 2000005
#define MOD 666013
using namespace std;
char s1 [DM], s2 [DM];
int answ [1005];
int hash [DM];
int nb (char c)
{
if (tolower (c) == c)
{
return (c -'a') + 26;
}
else
{
return c - 'A';
}
}
long long pw (long long a, long long b)
{
long long i, rez = 1;
for (i = 1; i <= b; ++ i)
{
rez *= a;
rez %= MOD;
}
return rez;
}
long long modineg (long long nb)
{
nb = nb % MOD;
if (nb < 0)
{
nb += MOD;
}
return nb;
}
int main()
{
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
long long j, hash1 = 0, n1, n2, i, base = 52, nrc = 0, bpn1m1, ans = 0; //bpn1m1 - base la puterea n1 minus 1
bool OK;
f >> s1 >> s2;
n1 = strlen (s1);
n2 = strlen (s2);
for (i = 0; i < n1; ++ i)
{
nrc = nrc + (( pw (base, (n1 - i - 1))) * nb (s2 [i]) % MOD) % MOD;
hash1 = hash1 + (( pw (base, (n1 - i - 1))) * nb (s1 [i]) % MOD) % MOD;
}
hash [0] = nrc;
bpn1m1 = pw (base, n1 - 1);
for (; i < n2; ++ i)
{
nrc = ( (modineg(nrc - ((bpn1m1 * nb (s2 [i - n1])) % MOD)) * base) % MOD + nb (s2 [i])) % MOD;
hash [i - n1 + 1] = nrc;
}
for (i = 0; i < n2 - n1; ++ i)
{
if (hash [i] == hash1)
{
OK = 1;
for (j = 0; j < n1 && OK; ++ j)
{
if (s1 [j] != s2 [i + j]) OK = 0;
}
if (OK)
{
if (ans < 1000)
{
answ [ans] = i;
}
ans ++;
}
}
}
g << ans << "\n";
for (i = 0; i < ans; ++ i)
g << answ [i] << " ";
g << "\n";
return 0;
}