Pagini recente » Cod sursa (job #321618) | Cod sursa (job #691736) | Cod sursa (job #1153514) | Cod sursa (job #2492289) | Cod sursa (job #531187)
Cod sursa(job #531187)
// 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 MAXN = 2000010;
const int B = 257;
char c,s[MAXN];
int n,m,a[MAXN],b[MAXN],hb,h,i,x;
vector<int> sol;
void verifica(int i)
{
int k;
for(k=1; k<=m; k++)
if(a[k+i-1] != b[k])
return;
sol.push_back(i);
}
int main()
{
in>>s;
m = strlen(s);
for(i=1; i<=m; i++)
b[i] = s[i-1];
in>>s;
n = strlen(s);
for(i=1; i<=n; i++)
a[i] = s[i-1];
h = hb = 0;
x=1;
for(i=1; i<m; i++)
x = (x*B)%MOD;
for(i=1; i<=m; i++)
{
hb = (B*hb + b[i])%MOD;
h = (B*h + a[i])%MOD;
}
if(hb == h)
verifica(1);
for(i=2; i<=n-m+1; i++)
{
h = (((h - (x*a[i-1])%MOD + MOD)*B)%MOD + a[i+m-1])%MOD;
if(h == hb)
verifica(i);
}
//out<<x<<endl;
//out<<hb<<endl;
//for(i=1; i<=n-m+1; i++)
// out<<h[i]<<' ';
out<<sol.size()<<'\n';
for(i=0; i<sol.size(); i++)
out<<sol[i]-1<<' ';
return 0;
}