Pagini recente » Cod sursa (job #1779845) | Cod sursa (job #714827) | Cod sursa (job #373192) | Cod sursa (job #3244223) | Cod sursa (job #1369073)
#include<iostream>
#include<fstream>
#include<string.h>
#include<vector>
#define NMAX 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[NMAX],p[NMAX];
int urm[NMAX],n,m;
void prefix(char *p)
{
int k=0,i;
urm[1]=0;
for(i=2;i<=m;i++)
{
while(k&&p[k+1]!=p[i])k=urm[k];
if(p[k+1]==p[i])
k++;
urm[i]=k;
}
}
int main()
{
fin.getline(p+1,NMAX);
fin.getline(s+1,NMAX);
m=strlen(p+1);
n=strlen(s+1);
prefix(p);int k=0;
vector<int>sol;
for(int i=1;i<=n;i++)
{
while(k&&p[k+1]!=s[i])k=urm[k];
if(p[k+1]==s[i])
k++;
if(k==m)
{
sol.push_back(i-m);
k=urm[k];
}
}
fout<<sol.size()<<'\n';
for(int i=0;i<sol.size()&&i<=1000;++i)
fout<<sol[i]<<" ";
fin.close();
fout.close();
return 0;
}