Pagini recente » Cod sursa (job #3363219) | Cod sursa (job #3363175) | Cod sursa (job #3361364) | Cod sursa (job #3363218) | Cod sursa (job #3363187)
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int ans[1001];
int hash_b[2000002];
const int MOD=100000007;
const int B=31;
int expo(int a,int i)
{
if (i==0)
{
return 1;
}
else
{
if (i%2==0)
{
int rasp=expo(a,i/2);
return rasp*rasp;
}
if (i%2==1)
{
return a*expo(a,i-1);
}
}
}
int main()
{
int hash_a,numere=0;
string a;
string b;
fin >> a >> b;
for (int i=0;i<a.size();i++)
{
if (a[i]>=48 && a[i]<=57)
{
hash_a+=(a[i]-48)*expo(B,i);
}
if (a[i]>=65 && a[i]<=90)
{
hash_a+=(a[i]-(65-57))*expo(B,i);
}
if (a[i]>=97 && a[i]<=122)
{
hash_a+=(a[i]-(122-90-(65-57)))*expo(B,i);
}
}
for (int i=0;i<b.size();i++)
{
if (a[i]>=48 && a[i]<=57)
{
if (i!=0)
{
hash_b[i]=hash_b[i-1]+(b[i]-48)*expo(B,i);
}
}
if (a[i]>=65 && a[i]<=90)
{
if (i!=0)
{
hash_b[i]=hash_b[i-1]+(b[i]-(65-57))*expo(B,i);
}
}
if (a[i]>=97 && a[i]<=122)
{
if (i!=0)
{
hash_b[i]=hash_b[i-1]+(b[i]-(122-90-(65-57)))*expo(B,i);
}
}
}
for (int i=0;i+a.size()-1<b.size() && numere<=1000;i++)
{
if (i==0)
{
if (hash_b[i+a.size()-1]/expo(B,i)==hash_a)
{
numere++;
ans[numere]=i;
}
}
else
{
if ((hash_b[i+a.size()-1]-hash_b[i-1])/expo(B,i)==hash_a)
{
numere++;
ans[numere]=i;
}
}
}
fout << numere << '\n';
for (int i=1;i<=numere;i++)
{
fout << ans[i] << ' ';
}
return 0;
}