Pagini recente » Cod sursa (job #2979702) | Cod sursa (job #2984867) | Cod sursa (job #3173483) | Cod sursa (job #955407) | Cod sursa (job #1589674)
#include <fstream>
#include <vector>
#include <cstring>
#define NMAX 2000005
using namespace std;
char s1[NMAX],s2[NMAX];
int ant[NMAX];
int n,m,i,k,nr,l1,l2;
vector<int>sol;
void prefix()
{
int i;
k=0;ant[1]=0;
for(i=2;i<=l1;++i)
{
while(s1[k+1]!=s1[i] && k>0) k=ant[k];
if(s1[k+1] == s1[i]) ++k;
ant[i]=k;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(s1+1,NMAX);
f.getline(s2+1,NMAX);
l1=strlen(s1+1);
l2=strlen(s2+1);
prefix();
k=0;
for(i=1; i<=l2; ++i)
{
while(s1[k+1] != s2[i] && k>0) k=ant[k];
if(s1[k+1] == s2[i]) ++k;
if(k == l1)
{
++nr;
if(nr <= 1000)
{
sol.push_back(i-l1);
}
}
}
g<<nr<<"\n";
for(i=0; i<sol.size(); ++i)
g<<sol[i]<<" ";
return 0;
}