Pagini recente » Cod sursa (job #2170076) | Cod sursa (job #1492731) | Cod sursa (job #377249) | Cod sursa (job #1025447) | Cod sursa (job #1229200)
#include <fstream>
#include <string.h>
#include <cstdio>
#define modf 100007
#define mods 100021
#define NMax 2000001
#define bs 73
using namespace std;
ofstream g("strmatch.out");
int hashf, hashs, p1, p2, foundf, founds, n, poz[1001], i;
char a[NMax], b[NMax];
int main()
{
freopen("strmatch.in", "r", stdin);
scanf("%s %s", a, b);
p1=1;
p2=1;
for (i=0; i<strlen(a); i++) {
hashf=(hashf*bs+a[i])%modf;
hashs=(hashs*bs+a[i])%mods;
if (i==0)
continue;
p1=(p1*bs)%modf;
p2=(p2*bs)%mods;
}
if (strlen(a) > strlen(b)) {
g<<"0\n";
return 0;
}
for (i=0; i<strlen(b); i++) {
foundf=((foundf-(p1*b[i-strlen(a)])%modf+modf)*bs+b[i])%modf;
founds=((founds-(p2*b[i-strlen(a)])%mods+mods)*bs+b[i])%mods;
if (foundf==hashf && founds==hashs)
poz[++n]=i-strlen(a)+1;
}
g<<n<<"\n";
for (i=1; i<=n && i<=1000; i++)
g<<poz[i]<<" ";
return 0;
}