Pagini recente » Cod sursa (job #323856) | Cod sursa (job #967331) | Cod sursa (job #1473852) | Cod sursa (job #742471) | Cod sursa (job #1799280)
#include <bits/stdc++.h>
using namespace std;
#define DD 256
vector <int> ar;
void searcsh (string pat,string txt,int q)
{
int len1 = pat.size();
int len2 = txt.size();
int i,j;
int p = 0,t{0},h{1};
for (int i = 0;i<len1-1;i++)
h = (h*DD)%q;
for (i = 0;i<len1;i++)
{
p = (DD*p + pat[i])%q;
t = (DD*t + txt[i])%q;
}
for (i = 0;i<=len2 - len1;i++)
{
if (p == t)
{
for (j=0;j<len1;j++)
if (txt[i+j] != pat[j])
break;
if (j == len1)
ar.push_back(i);
}
if (i<len1-len2)
{
t = (DD*(t-txt[i]*h)) + txt[i+len2]%q;
if (t<0)
t+=q;
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
string a,b;
getline(cin,a);
getline(cin,b);
searcsh(a,b,101);
printf("%d\n",ar.size());
for (int i=0;i<ar.size();i++)
printf("%d ",ar[i]);
return 0;
}