Pagini recente » Cod sursa (job #2596449) | Cod sursa (job #1184249) | Cod sursa (job #1263150) | Cod sursa (job #2113132) | Cod sursa (job #2066848)
#include <cstdio>
#include <cstring>
#include <vector>
#define mod 101
#define N 2000005
using namespace std;
char sir_init[N], sir[N], puteri_123[N], puteri_24[N];
int init_hash_1, init_hash_2, tmp_hash_1, tmp_hash_2, l_sir_init;
vector <int> vec;
void creare_puteri(int baza, char vec[])
{
vec[0] = 1;
for(int i = 1 ; i < l_sir_init ; ++i)
{
vec[i] = (vec[i - 1] * baza) % mod;
}
}
void create_hash(char putere[], int &x, char vec[], int finish)
{
for(int i = 0 ; i < finish ; ++i)
{
x += (vec[i] * putere[finish - 1 - i]) % mod;
x %= mod;
}
}
int comparare(int start)
{
if(init_hash_1 == tmp_hash_1)
{
if(init_hash_2 == tmp_hash_2)
{
if!(strncmp(sir_init, sir + start, l_sir_init))
{
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);
creare_puteri(123,puteri_123);
creare_puteri(24,puteri_24);
create_hash(puteri_123, init_hash_1, sir_init, l_sir_init);
create_hash(puteri_24, init_hash_2, sir_init, l_sir_init);
create_hash(puteri_123, tmp_hash_1, sir, l_sir_init);
create_hash(puteri_24, tmp_hash_2, sir, l_sir_init);
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] * puteri_123[l_sir_init - 1]) % mod)) * 123) % mod + sir[i + l_sir_init - 1]) % mod;
tmp_hash_2 = (((tmp_hash_2 - ((sir[i - 1] * puteri_24[l_sir_init - 1]) % 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();
printf("\n");
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
}