Pagini recente » Cod sursa (job #2057369) | Cod sursa (job #677159) | Cod sursa (job #1305319) | Cod sursa (job #668244) | Cod sursa (job #2063390)
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#define MOD 101
using namespace std;
string txt,p;
vector <int> putere,sol;
int h,l,lt,put;
int rp(int n,int p)
{
int r=1;
while(p!=0)
{
if(p%2==0)
{
n=(n*n)%MOD;
p=p/2;
}
else
{
r=(r*n)%MOD;
p=p-1;
}
}
return r;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
getline(cin,p);
getline(cin,txt);
l=p.length();
lt=txt.length();
put=1;
h=p[0]%MOD;
int loc=txt[0]%MOD;
for(int i=1;i<l;i++)
{
h=(h*256+p[i])%MOD;
put=put*256%MOD;
loc=(loc*256+txt[i])%MOD;
}
for(int i=l;i<lt;i++)
{
if(loc==h)
{
if(p==txt.substr(i-l,l))
sol.push_back(i-l);
}
loc=(((loc-(txt[i-l]*put%101)+101)*256%101)+txt[i])%101;
}
if(loc==h)
{
if(p==txt.substr(lt-l,l))
sol.push_back(lt-l);
}
int ll=sol.size();
cout<<ll<<"\n";
ll=min(ll,1000);
for(int i=0;i<ll;i++)
cout<<sol[i]<<" ";
return 0;
}