Pagini recente » Cod sursa (job #1726059) | Cod sursa (job #2368728) | Cod sursa (job #1064286) | Cod sursa (job #852970) | Cod sursa (job #1922313)
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#define maxSize 2000001
#define prim 73
#define mod 104729
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s1[maxSize], s2[maxSize];
queue <int> q;
int main()
{
fin.getline(s1, maxSize);
fin.getline(s2, maxSize);
int l1 = strlen(s1) - 1;
int l2 = strlen(s2) - 1;
long long hash1 = 0, hash2 = 0, power = 1;
int value = 'A' - 1;
hash1 = s1[0] - value;
hash2 = s2[0] - value;
for(int i = 1; i <= l1; i++) {
power = (power * prim) % mod;
hash1 = (hash1 + (s1[i] - value) * power)% mod;
hash2 = (hash2 + (s2[i] - value) * power)% mod;
}
int nr = 0;
for (int i = l1 + 1; i <= l2; i++) {
if(hash2 == hash1) {
nr++;
q.push(i - l1 -1);
}
hash2 = (((hash2 - (s2[i - l1 - 1] - value)) / prim) + ((s2[i] - value) * power) % mod) % mod;
}
fout<<nr<<'\n';
while(!q.empty()) {
fout<<q.front()<<' ';
q.pop();
}
fin.close();
fout.close();
return 0;
}