Pagini recente » Cod sursa (job #633208) | Cod sursa (job #2025277) | Cod sursa (job #2870629) | Cod sursa (job #1858270) | Cod sursa (job #2237859)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,p;
long long n,m,i,hs,hp,N,a[1024],rh(ll, ll, string);
bool verify(ll, ll);
int main()
{
f>>p>>s;
n=s.size();
m=p.size();
if(m>n)
{
g<<"0\n";
return 0;
}
hp=rh(0,p.size(),p);
for(i=0; i<n-m+1; i++)
{
hs=rh(i,i+m,s);
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;
}
ll rh(ll start, ll finish, string k)
{
ll j,ret=(int)k[start];
for(j=start+1; j<finish; j++)
{
ret=(ret%101)*256;
ret+=(int)k[j];
}
return ret%101;
}
bool verify(ll start, ll finish)
{
ll j;
for(j=0; j<m; j++)
if(p[j]!=s[i+j])
return false;
return true;
}