Pagini recente » Cod sursa (job #758247) | Cod sursa (job #1301514) | Cod sursa (job #603976) | Cod sursa (job #1493090) | Cod sursa (job #1090744)
#include <fstream>
#include <cstring>
#include <queue>
#define NMAX 2000005
using namespace std;
//CU KMP
FILE* f=freopen("strmatch.in","r",stdin);
FILE* o=freopen("strmatch.out","w",stdout);
char str[NMAX],sub[NMAX];
int n,m,num;
int pad[NMAX];
queue<int> sol;
void Reading()
{
scanf("%s\n%s",sub,str);
n=strlen(str);
m=strlen(sub);
sub[m]='#';
}
void InitPad()
{
pad[0]=-1;
int i=2,k=0;
while(i<=m)
if(sub[i-1]==sub[k])
k+=1,pad[i]=k,i+=1;
else if(k)
k=pad[k];
else
pad[i]=0,i+=1;
}
int main()
{
Reading();
if(m>n) { printf("0"); return 0; }
InitPad();
int k=0;
for(int i=0;k+i<n;)
{
if(str[k+i]==sub[i]) {
if(i==m-1)
{ num+=1; if(num<1000) sol.push(k); }
i+=1;
}
else {
k+=i-pad[i];
i=(pad[i]>-1)?pad[i]:0;
}
}
printf("%d\n",num);
while(!sol.empty()) { printf("%d ",sol.front()); sol.pop(); }
return 0;
}