Pagini recente » Cod sursa (job #693876) | Rating Kononov Daniil (dextar) | Cod sursa (job #1773869) | Cod sursa (job #2486945) | Cod sursa (job #2237864)
#include <bits/stdc++.h>
#define ll long long
#define MOD 101
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,p;
long long n,m,i,hs,hp,h,N,a[1024];
bool verify(ll, ll);
int main()
{
f>>p>>s;
n=s.size();
m=p.size();
if(m>n)
{
g<<"0\n";
return 0;
}
hp=(int)p[0]%MOD,hs=(int)s[0]%MOD;
for(i=1; i<p.size(); i++)
{
hp%=MOD,hs%=MOD;
hp*=256,hs*=256;
hp+=p[i],hs+=s[i];
}
hp%=MOD,hs%=MOD;
if(hp==hs)
{
if(verify(0,m))
{
N++,a[N]=0;
}
}
for(i=1; i<n-m+1; i++)
{
hs=(((hs+101)-((int)s[i-1])*((256%101)*256)%101)*256 + (int)s[i+m-1])%101;
if(hp==hs)
{
if(verify(i,i+m))
{
N++;
if(N<=1000)
a[N]=i;
}
}
}
g<<N<<'\n';
for(i=1; i<=N; i++)
g<<a[i]<<' ';
return 0;
}
bool verify(ll start, ll finish)
{
ll j;
for(j=0; j<m; j++)
if(p[j]!=s[start+j])
return false;
return true;
}