Pagini recente » Cod sursa (job #1764715) | Cod sursa (job #2636084) | Cod sursa (job #1881584) | Cod sursa (job #845859) | Cod sursa (job #2067271)
#include <cstdio>
#include <cstring>
#include <vector>
#define mod 101
#define N 2000005
using namespace std;
int init_hash_1, init_hash_2, tmp_hash_1, tmp_hash_2, l_sir_init, putere_123, putere_24;
char sir_init[N], sir[N];
vector <int> vec;
void create_hash(int baza, int &x, char vec[], int &putere)
{
putere = 1;
for(int i = l_sir_init - 1 ; i >= 0 ; --i)
{
x += (vec[i] * putere) % mod;
x %= mod;
if(i > 0)
{
putere *= baza;
putere %= mod;
}
}
}
int comparare(int start)
{
if(init_hash_1 == tmp_hash_1)
{
if(init_hash_2 == tmp_hash_2)
{
for(int i = start ; i < start + l_sir_init; ++i)
{
if(sir_init[i - start] != sir[i])
{
return 0;
}
}
return 1;
}
}
return 0;
}
void afisare()
{
printf("%d\n", vec.size());
for(int i = 0 ; i < vec.size() && i < 1000; ++i)
{
printf("%d ", vec[i]);
}
}
void solve()
{
l_sir_init = strlen(sir_init);
create_hash(123, init_hash_1, sir_init,putere_123);
create_hash(24, init_hash_2, sir_init,putere_24);
create_hash(123, tmp_hash_1, sir,putere_123);
create_hash(24, tmp_hash_2, sir,putere_24);
if(comparare(0))
{
vec.push_back(0);
}
int tmp_l = strlen(sir) - l_sir_init;
for(int i = 1 ; i < tmp_l ; ++i)
{
tmp_hash_1 = (((tmp_hash_1 - ((sir[i - 1] * putere_123) % mod)) * 123) % mod + sir[i + l_sir_init - 1]) % mod;
tmp_hash_2 = (((tmp_hash_2 - ((sir[i - 1] * putere_24) % mod)) * 24) % mod + sir[i + l_sir_init - 1]) % mod;
if(comparare(i))
{
vec.push_back(i);
}
}
afisare();
}
void citire()
{
fgets(sir_init,N,stdin);
fgets(sir,N,stdin);
if(sir_init[strlen(sir_init) - 1] == '\n')
{
sir_init[strlen(sir_init) - 1] = NULL;
}
if(sir[strlen(sir) - 1] == '\n')
{
sir[strlen(sir) - 1] = NULL;
}
solve();
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
}