Pagini recente » Cod sursa (job #2483446) | Cod sursa (job #2189818) | Cod sursa (job #104995) | Cod sursa (job #2428741) | Cod sursa (job #1487613)
#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
#include <string.h>
#define nmax 2000002
using namespace std;
char s[nmax],pattern[nmax];
int n,m;
int sol[nmax];
vector<int> v;
void read()
{
scanf("%s\n",&pattern);
scanf("%s",&s);
n=strlen(s);
m=strlen(pattern);
}
int Hash(char ss[nmax])
{
int value=0;
for(int i=0;i<m;i++)
value+=ss[i];
return value;
}
void solve()
{
int hs,hpattern;
hs=Hash(s);
hpattern=Hash(pattern);
for(int i=0;i<n-m+1;i++)
{
if(hs == hpattern)
{
int ok=1;
for(int j=0;j<m;j++)
if(s[i+j]!=pattern[j])
{ok=0;
break;}
if(ok)
v.push_back(i);
}
hs = hs - s[i]+s[i+m];
}
printf("%d\n",v.size());
int sol = v.size()<1000?v.size():1000;
for(int i=0;i<sol;i++)
printf("%d ",v[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read();
solve();
return 0;
}