Pagini recente » Cod sursa (job #831351) | Monitorul de evaluare | Cod sursa (job #680331) | Cod sursa (job #1924141) | Cod sursa (job #1229223)
#include <fstream>
#include <string.h>
#define modf 100007
#define mods 100021
#define NMax 2000001
#define bse 73
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int hashf, hashs, p1, p2, foundf, foundss, poz[NMax], i, n;
char a[NMax], b[NMax];
int main()
{
f.get(a, 2000001);
f.get();
f.get(b, 2000001);
p1=1;
p2=1;
for (i=0; i<strlen(a); i++) {
hashf=(hashf*bse+a[i])%modf;
hashs=(hashs*bse+a[i])%mods;
if (i!=0) {
p1=(p1*bse)%modf;
p2=(p2*bse)%mods;
}
}
if (strlen(a) > strlen(b)) {
g<<"0\n";
return 0;
}
for (i=0; i<strlen(a); i++) {
foundf=(foundf*bse+a[i])%modf;
foundss=(foundss*bse+a[i])%mods;
}
if (foundf==hashf && foundss==hashs) {
poz[0]=1;
n++;
}
for (i=strlen(a); i<strlen(b); i++) {
foundf=((foundf-(p1*b[i-strlen(a)])%modf+modf)*bse+b[i])%modf;
foundss=((foundss-(p2*b[i-strlen(a)])%mods+mods)*bse+b[i])%mods;
if (foundf==hashf && foundss==hashs) {
poz[i-strlen(a)+1]=1;
n++;
}
}
g<<n<<"\n";
n=0;
for (i=0; i<strlen(b) && n<1000; i++)
if (poz[i]==1) {
g<<i<<" ";
n++;
}
g<<"\n";
return 0;
}