Pagini recente » Cod sursa (job #256900) | Cod sursa (job #1237475) | Cod sursa (job #2352830) | Cod sursa (job #2117530) | Cod sursa (job #531197)
Cod sursa(job #531197)
// infoarena: problema/strmatch //
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MOD = 666013;
const int MOD2 = 100007;
const int MAXN = 3000010;
const int B = 257;
char c,a[MAXN],b[MAXN];
int n,m,hb,h,i,x,x2,hb2,h2;
int sol[MAXN];
int verifica(int i)
{
int k;
for(k=0; k<m; k++)
if(a[k+i] != b[k])
return 0;
return sol[++sol[0]] = i;
}
int main()
{
in>>b;
m = strlen(b);
in>>a;
n = strlen(a);
x=x2=1;
for(i=1; i<m; i++)
x = (x*B)%MOD,
x2 = (x2*B)%MOD2;
for(i=0; i<m; i++)
{
hb = (B*hb + b[i])%MOD;
hb2 = (B*hb2 + b[i])%MOD2;
h = (B*h + a[i])%MOD;
h2 = (B*h2 + a[i])%MOD2;
}
if(hb == h && hb2 == h2)
sol[++sol[0]] = 0;
for(i=1; i<=n-m+1; i++)
{
h = (((h - (x*a[i-1])%MOD + MOD)*B) + a[i+m-1])%MOD;
h2 = (((h2 - (x2*a[i-1])%MOD2 + MOD2)*B) + a[i+m-1])%MOD2;
if(h == hb && h2 == hb2)
sol[++sol[0]] = i;
}
out<<sol[0]<<'\n';
for(i=1, x=min(sol[0], 1000); i<=x; i++)
out<<sol[i]<<' ';
return 0;
}