Pagini recente » Rating Jasmina Cornestean (JasminaCornestean) | Cod sursa (job #1786626) | Cod sursa (job #2644831) | Cod sursa (job #1746138) | Cod sursa (job #3036449)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define P 73
#define MOD1 100007
#define MOD2 100021
int slg, tlg, P1, P2, hashA1, hashA2;
int main(){
string s, t;
fin >> s >> t;
slg=s.length();
tlg=t.length();
P1=P2=1;
for (int i = 0; i < slg; i++)
{
hashA1 = (hashA1 * P + s[i]) % MOD1;
hashA2 = (hashA2 * P + s[i]) % MOD2;
if (i != 0)
P1 = (P1 * P) % MOD1,
P2 = (P2 * P) % MOD2;
}
int hash1=0, hash2=0;
for (int i = 0; i < slg; i++)
hash1 = (hash1 * P + t[i]) % MOD1,
hash2 = (hash2 * P + t[i]) % MOD2;
int ans=0;
queue<int> q;
if(hash1==hashA1 && hash2==hashA2){
ans++;
q.push(0);
}
for(int i=slg; i<tlg; i++){
hash1 = ((hash1 - (t[i - slg] * P1) % MOD1 + MOD1) * P + t[i]) % MOD1;
hash2 = ((hash2 - (t[i - slg] * P2) % MOD2 + MOD2) * P + t[i]) % MOD2;
if(hash1==hashA1 && hash2==hashA2){
q.push(i-slg+1);
ans++;
}
}
fout << ans << '\n';
for(int i=0; i<1000 && !q.empty(); i++){
fout << q.front() << ' '; q.pop();
}
}