Pagini recente » Cod sursa (job #2473750) | Cod sursa (job #2182642) | Cod sursa (job #1465141) | Cod sursa (job #89366) | Cod sursa (job #1646449)
#include <fstream>
#include <vector>
#include <cstring>
#define NMAX 100005
using namespace std;
char s[NMAX],p[NMAX];
int n,m,i,j,ant[NMAX],nr,k;
vector<int>sol;
void prefix()
{
int i;
k=0;ant[1]=0;
for(i=2;i<=n;++i)
{
while(p[k+1] != p[i] && k>0) k=ant[k];
if(p[k+1] == p[i]) ++k;
ant[i]=k;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(p+1,NMAX);
f.getline(s+1,NMAX);
n=strlen(p+1);
m=strlen(s+1);
prefix();
k=0;
for(i=1;i<=m;++i)
{
while(s[i] != p[k+1] && k > 0) k=ant[k];
if(p[k+1] == s[i]) ++k;
if(k == n)
{
++nr;
if(nr < 1000) sol.push_back(i-n);
}
}
g<<nr<<"\n";
for(i=0;i<sol.size();++i) g<<sol[i]<<" ";
return 0;
}