Pagini recente » Cod sursa (job #2559938) | Cod sursa (job #2766331) | Cod sursa (job #2410152) | Cod sursa (job #1113052) | Cod sursa (job #1391666)
#include <fstream>
#include <vector>
#include <cstring>
#define NMAX 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char p[NMAX],t[NMAX];
int n,m,pre[NMAX];
void constr_prefix();
vector <int> sol;
int main()
{
int i,x=-1;
fin>>p; fin>>t;
n=strlen(t); m=strlen(p);
constr_prefix();
for (i=0; i<n; i++)
{
while (x!=-1 && p[x+1]!=t[i]) x=pre[x];
if (p[x+1]==t[i]) x++;
if (x==m-1)
{
sol.push_back(i-m+1);
x=pre[x];
}
}
fout<<sol.size()<<'\n';
for (i=0; i<sol.size() && i<1000; i++) fout<<sol[i]<<' ';
fout<<'\n';
fout.close();
fin.close();
return 0;
}
void constr_prefix()
{
int k=-1,x;
pre[0]=0;
for (x=1;x<m; x++)
{
while (k>0 && p[k+1]!=p[x]) k=pre[k];
if (p[k+1]==p[x]) k++;
pre[x]=k;
}
}