Pagini recente » Cod sursa (job #2443656) | Cod sursa (job #2340841) | Cod sursa (job #677535) | Cod sursa (job #591752) | Cod sursa (job #2100974)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
const int NMAX=1e6*2+5;
string A,B;
int n,h,k,S[NMAX];
vector <int> sol;
int main()
{
fi>>A;
fi>>B;
n=A.size();
h=B.size();
A="#"+A;
B="#"+B;
S[0]=-1;
S[1]=0;
k=0;
for(int i=2;i<=n;i++)
{
while(k>0 && A[i]!=A[k+1])
k=S[k];
if(A[i]==A[k+1])
k++;
S[i]=k;
}
k=0;
for(int i=1;i<=h;i++)
{
while(k>0 && B[i]!=A[k+1])
k=S[k];
if(B[i]==A[k+1])
k++;
if(k==n)
{
sol.push_back(i-k);
k=S[k];
}
}
fo<<sol.size()<<"\n";
if(sol.size()>1000)
n=1000;
else
n=sol.size();
for(int i=0;i<n;i++)
fo<<sol[i]<<" ";
fi.close();
fo.close();
return 0;
}