Pagini recente » Cod sursa (job #3159749) | Cod sursa (job #2689339) | Cod sursa (job #2742811) | Cod sursa (job #1546422) | Cod sursa (job #3157193)
#include <bits/stdc++.h>
#define N 2000000
#define B 127
#define MOD 666013
using namespace std;
/// cautam aparitiile lui a in b
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[N + 5], b[N + 5];
int nr_ap, poz[1005];
int len_a, len_b;
bool Match(int st)
{
for(int i = 0; i < len_a; ++i)
if(a[i] != b[st + i]) return 0;
return 1;
}
int main()
{
fin >> a >> b;
int first_ch = 1;
int pattern_hash = 0;
len_a = strlen(a);
len_b = strlen(b);
if(len_a > len_b) {cout << 0; return 0;}
/// calculam valoarea aferenta lui A
for(int i = len_a - 1; i >= 0; --i)
{
pattern_hash = (pattern_hash % MOD + (int(a[i]) * first_ch) % MOD) % MOD;
first_ch = (first_ch * B) % MOD;
}
first_ch = 1;
for(int i = 1; i < len_a; ++i)
first_ch = (first_ch * B) % MOD;
int current_hash = 0;
int pow = 1;
/// calculam valoarea primei ferestre
for(int i = len_a - 1; i >= 0; --i)
{
current_hash = (current_hash % MOD + (int(b[i]) * pow) % MOD) % MOD;
pow = (pow * B) % MOD;
}
/// verificam daca avem un match
if(current_hash == pattern_hash && Match(0))
poz[nr_ap++] = 0;
/// calculam pt restul ferestrelor
for(int i = len_a; i < len_b; ++i)
{
if(current_hash <= int(b[i - len_a]) * first_ch)
{
int ct = (int(b[i - len_a]) * first_ch - current_hash) / MOD;
current_hash += (ct + 1) * MOD; // tb liniarizat
}
current_hash = (current_hash - int(b[i - len_a]) * first_ch) % MOD;
current_hash = (current_hash * B) % MOD; /// tot ce pastrez avanseaza cu o poz in stanga, deci puterea la care apare B creste cu 1 pt fiecare
current_hash = (current_hash % MOD + int(b[i]) % MOD) % MOD;
if(current_hash == pattern_hash && Match(i - len_a + 1) && nr_ap < 1000)
poz[nr_ap++] = i - len_a + 1;
}
fout << nr_ap << "\n";
for(int i = 0; i < nr_ap; ++i)
fout << poz[i] << " ";
return 0;
}