Pagini recente » Cod sursa (job #696932) | Cod sursa (job #2981426) | Cod sursa (job #65345) | Cod sursa (job #3139776) | Cod sursa (job #1463901)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
char p[2000010],s[2000010];
int q[2000010],poz[1010];
int main()
{
fstream f("strmatch.in",ios::in);
f.getline(p,2000010);
f.getline(s,2000010);
f.close();
f.open("strmatch.out",ios::out);
int i=1,j=0,lp=strlen(p),ls=strlen(s);
q[0]=0;
while(i<lp)
if(p[i]==p[j])
q[i++]=++j;
else if(j)
j=q[j-1];
else
q[i++]=0;
int n=0;
i=0;
j=0;
while(i<ls)
if(s[i]==p[j])
{
i++,j++;
if(j==lp)
{
n++;
if(n<=1000)
poz[n]=i-j;
}
}
else if(j)
j=q[j-1];
else
i++;
f<<n<<"\n";
for(i=1; i<=min(n,1000); i++)f<<poz[i]<<" ";
return 0;
}