Pagini recente » Cod sursa (job #1048931) | Cod sursa (job #47749) | Cod sursa (job #1745138) | Cod sursa (job #1749618) | Cod sursa (job #3208885)
#include <fstream>
#include <cstring>
#include <vector>
#define LMAX 2000001
#define BAZA 62
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
vector<int> ans;
const int MOD1 = 100007;
const int MOD2 = 100021;
char s1[LMAX], s2[LMAX];
int main()
{
in.get(s1, LMAX);
in.get();
in.get(s2, LMAX);
int k = strlen(s1);
int nrs1 = 0;
int nrs2 = 0;
int p1 = 1, p2 = 1;
for(int i = 0; i < k; i++){
nrs1 = (nrs1 * BAZA + s1[i]) % MOD1;
nrs2 = (nrs2 * BAZA + s1[i]) % MOD2;
if(i > 0){
p1 = p1 * BAZA % MOD1;
p2 = p2 * BAZA % MOD2;
}
}
int n = strlen(s2);
if(k > n)
out << 0;
else{
int nr1 = 0, nr2 = 0;
for(int i = 0; i < k; i++){
nr1 = (nr1 * BAZA + s2[i]) % MOD1;
nr2 = (nr2 * BAZA + s2[i]) % MOD2;
}
if(nr1 == nrs1 && nr2 == nrs2)
ans.push_back(0);
for(int i = k; i < n; i++){
nr1 = ((nr1 - (s2[i - k] * p1) % MOD1 + MOD1) * BAZA + s2[i]) % MOD1;
nr2 = ((nr2 - (s2[i - k] * p2) % MOD2 + MOD2) * BAZA + s2[i]) % MOD2;
if(nr1 == nrs1 && nr2 == nrs2)
ans.push_back(i - k + 1);
}
}
out << ans.size() << "\n";
n = ans.size();
if(n > 1000)
n = 1000;
for(int i = 0; i < n; i++)
out << ans[i] << " ";
return 0;
}