Pagini recente » Cod sursa (job #2391770) | Cod sursa (job #2243182) | Cod sursa (job #1853328) | Cod sursa (job #2972595) | Cod sursa (job #462586)
Cod sursa(job #462586)
#include<fstream>
#include<cstring>
using namespace std;
char p[2000001], v[2000001];
int np[2000001], m, n, val[1001];
void prefix()
{
int i, x=-1;
np[0]=-1;
for(i=1; i<m; ++i)
{
while(x>0 && v[x + 1]!=v[i]) x=np[x];
if(v[x + 1]==v[i])
x++;
np[i]=x;
}
}
int main()
{
int x=-1, i, nrpos=0, k=0;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(p, 2000000);
f.getline(v, 2000000);
n=strlen(v)-1; m=strlen(p)-1;
prefix();
for(i=0; i<=n; ++i)
{
while(x>-1 && p[x+1]!=v[i])
x=np[x];
if(p[x+1]==v[i])
x++;
if(x == m)
{
x=np[m];
if(k<=1000)
{
val[k]=i-m;
++k;
}
nrpos++;
}
}
g<<nrpos<<'\n';
for(i=0; i<k; ++i)
g<<val[i]<<' ';
g<<'\n';
g.close();
return 0;
}