Pagini recente » Cod sursa (job #1672320) | Cod sursa (job #268929) | Cod sursa (job #3138443) | Cod sursa (job #3187693) | Cod sursa (job #462588)
Cod sursa(job #462588)
#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>-1 && p[x + 1]!=p[i]) x=np[x];
if(p[x + 1]==p[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;
}