Pagini recente » Cod sursa (job #1705746) | Profil Rodik_Rody | Cod sursa (job #1746916) | Cod sursa (job #1572974) | Cod sursa (job #1410009)
#include <bits/stdc++.h>
using namespace std;
#ifdef INFOARENA
ifstream f("strmatch.in");
#define cout g
#else
ifstream f("date.in");
#endif // INFOARENA
ofstream g("strmatch.out");
#define nmax 2000001
#define MOD1 999981
#define MOD2 999983
#define nr(a) (a-'0')
#define BASE 75
char A[nmax],B[nmax];
int pref[nmax],n,m,k,pos,i,hash1_A,hash2_A,hash1_B,hash2_B,P1,P2;
vector <int> sol;
int main()
{
f>>A+1>>B+1;
n=strlen(A+1);
m=strlen(B+1);
if(m<n)
{
cout<<0;
return 0;
}
P1=P2=1;
for(i=1;i<=n;++i)
{
hash1_A = (hash1_A * BASE + nr(A[i])) % MOD1;
hash2_A = (hash2_A * BASE + nr(A[i])) % MOD2;
hash1_B = (hash1_B * BASE + nr(B[i])) % MOD1;
hash2_B = (hash2_B * BASE + nr(B[i])) % MOD2;
if(i>1)
{
P1 =1ll*P1 * BASE % MOD1;
P2 =1ll*P2 * BASE % MOD2;
}
}
if(hash1_A==hash1_B && hash2_A == hash2_B) sol.push_back(0);
for(i=n+1;i<=m;++i)
{
hash1_B =1ll*((hash1_B - 1ll*nr(B[i-n]) * P1 % MOD1 + MOD1) * BASE + nr(B[i])) % MOD1;
hash2_B =1ll*((hash2_B - 1ll*nr(B[i-n]) * P2 % MOD2 + MOD2) * BASE + nr(B[i])) % MOD2;
if(hash1_A==hash1_B && hash2_A == hash2_B) sol.push_back(i-n);
}
int x=0;
cout<<sol.size()<<'\n';
for(auto i:sol)
{
cout<<i<<' ';
if(++x>=1000) break;
}
return 0;
}