Pagini recente » Monitorul de evaluare | Cod sursa (job #1300887) | Cod sursa (job #1803622) | Cod sursa (job #2669069) | Cod sursa (job #2369529)
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
typedef long long ll;
const ll MOD=1000000007;
const ll P=997898399;
string a,b;
ll hashish;
ll p[NMAX],h[NMAX];
void precalculate()
{
h[0]=b[0];
for(int i=0;i<b.length();i++)
h[i]=(h[i-1]*P+b[i])%MOD;
p[0]=1;
for(int i=1;i<b.length();i++)
p[i]=(p[i-1]*P)%MOD;
hashish=a[0];
for(int i=1;i<a.length();i++)
hashish=(hashish*P+a[i])%MOD;
}
int nr;
inline ll hashing(int st,int dr)
{
if(st==0) return h[dr];
return (h[dr]-(h[st-1]*p[dr-st+1])%MOD)%MOD;
}
int main()
{
fin>>a>>b;
vector<int> poz;
int aL=a.length();
int bL=b.length();
precalculate();
// fout<<hashish<<" "<<hashing(5,7);
for(int i=0;i<=bL-aL;i++)
{
if(hashish==hashing(i,i+aL-1))
{
nr++;
poz.push_back(i);
}
}
fout<<nr<<'\n';
for(auto x:poz)
fout<<x<<' ';
return 0;
}