Pagini recente » Cod sursa (job #1965801) | Cod sursa (job #2502030) | tema | Cod sursa (job #2438792) | Cod sursa (job #2572855)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMAX 805
#define mod 666023
#define p 73
char a[NMAX];
char b[NMAX];
int m,n;
long long po[NMAX];
vector<int> occ;
void rubin(char a[],char b[])
{
long long curr_h = 0;
int siz = max(n,m);
vector<int> hash(siz+1,0);
po[0] = 1;
for(int i=1;i<=siz;i++)
{
po[i] = (po[i-1] * p ) % mod;
}
//for(int i=1;i<=n;i++)
//cout<<hash[i]<<" ";
for(int i=0;i<m;i++)
{
if(a[i] >= 'A' && a[i]<= 'Z')
{
curr_h = (curr_h + (a[i]-'A'+1) * po[i] ) % mod;
}
else if(a[i] >= 'a' && a[i] <= 'z')
{
curr_h = (curr_h + (a[i]-'a'+1) * po[i] ) % mod;
}
else
curr_h = (curr_h + (a[i]-'0'+1) * po[i] ) % mod;
}
for(int i=0;i<n;i++)
{
if(b[i] >= 'A' && b[i]<= 'Z')
{
hash[i+1] = (hash[i] + (b[i]-'A'+1)*po[i] ) % mod;
}
else if(b[i] >= 'a' && b[i] <= 'z')
{
hash[i+1] = (hash[i] + (b[i]-'a'+1)*po[i] ) % mod;
}
else
hash[i+1] = (hash[i] + (b[i]-'0'+1)*po[i] ) % mod;
}
for(int i=0;i<n-m+1 && occ.size() < 1001;i++)
{
long long h = (hash[i+m]-hash[i] + mod) % mod;
if(h == (curr_h * po[i]) % mod )
occ.push_back(i);
}
}
int main()
{
fin.getline(a,NMAX);
fin.getline(b,NMAX);
m = strlen(a);
n = strlen(b);
if(m>n)
{
fout<<0;
return 0;
}
else
{
rubin(a,b);
fout<<occ.size()<<'\n';
for(int i=0;i<occ.size();i++)
fout<<occ[i]<<" ";
}
return 0;
}