Pagini recente » Cod sursa (job #654977) | Cod sursa (job #1140420) | Cod sursa (job #1411063) | Cod sursa (job #1085325) | Cod sursa (job #2862334)
#include <fstream>
#include <string>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
const int mod=666133;
const int mod2=666134;
int v[2000001];
string a, b;
int main()
{
long long a1=0, b1=0, a2=0, b2=0, r=0, h=1, h2=1, g;
int t=1;
cin >> a >> b;
g='z'-'0'+2;
for (int i=1; i<a.length(); i++)
{
h=(h*g)%mod;
h2=(h2*g)%mod2;
}
for (int i=0; i<a.length(); i++)
{
a1=(a1*g+a[i]-'0')%mod;
a2=(a2*g+a[i]-'0')%mod2;
}
for (int i=0; i<a.length(); i++)
{
b1=(b1*g+b[i]-'0')%mod;
b2=(b2*g+b[i]-'0')%mod2;
}
if (b1==a1 && b2==a2)
{
r++;
v[t++]=0;
}
for (int i=a.length(); i<b.length(); i++)
{
b1=((b1-h*(b[i-a.length()]-'0'))%mod+mod)%mod;
b1=(b1*g+b[i]-'0')%mod;
b2=((b2-h2*(b[i-a.length()]-'0'))%mod2+mod2)%mod2;
b2=(b2*g+b[i]-'0')%mod2;
if (b1==a1 && b2==a2)
{
r++;
v[t++]=i-a.length()+1;
}
}
cout << r << "\n";
for (int i=1; i<min(t, 1000); i++)
{
cout << v[i] << " ";
}
return 0;
}