Pagini recente » Cod sursa (job #1818495) | Cod sursa (job #1319997) | Cod sursa (job #3131431) | Cod sursa (job #731606) | Cod sursa (job #2849466)
///#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const ll MOD1 = 1e6+21,
MOD2 = 1e6+7,
P = 73,
SIZE = 2e6+10;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
/// ABA = A*73^3+B*73^2+A*73
ll hash1, hash2;
ll P1=1, P2=1;
char s1[SIZE], s2[SIZE];
int s1n, s2n;
vector <int> rez;
int cnt;
ll formHash(ll chash, char ch, ll mod)
{
return (chash*P+ch)%mod;
}
ll updateHash(ll chash, char in, char out, ll mod, ll SP)
{
return ((chash-(out*SP)%mod+mod)*P+in)%mod;
}
int main()
{
cin>>(s2+1)>>(s1+1);
s1n = strlen(s1+1);
s2n = strlen(s2+1);
for(int i=1; i<=s2n; i++) {
hash1 = formHash(hash1, s2[i], MOD1);
hash2 = formHash(hash2, s2[i], MOD2);
if(i>1) P1=(P1*P)%MOD1, P2=(P2*P)%MOD2;
}
ll chash1=0, chash2=0;
for(int i=1; i<=s2n; i++)
chash1 = formHash(chash1, s1[i], MOD1),
chash2 = formHash(chash2, s1[i], MOD2);
if(chash1==hash1 && chash2==hash2) {
rez.push_back(1);
++cnt;
}
for(int i=s2n+1; i<=s1n; i++) {
chash1 = updateHash(chash1, s1[i], s1[i-s2n], MOD1, P1);
chash2 = updateHash(chash2, s1[i], s1[i-s2n], MOD2, P2);
if(chash1==hash1 && chash2==hash2) {
if(cnt<1000) rez.push_back(i-s2n);
++cnt;
}
}
cout<<cnt<<'\n';
for(auto i : rez) cout<<i<<' ';
return 0;
}