Pagini recente » Cod sursa (job #3224440) | Cod sursa (job #737093) | Cod sursa (job #2188267) | Cod sursa (job #2626085) | Cod sursa (job #1508917)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000010],B[2000010];
int urm[2000010];
vector<int> h;
void urmat(int n)
{
int k=-1,x;
urm[0]=0;
for(x=1;x<n;x++)
{
while(k>0 && A[k+1]!=A[x]) k=urm[k];
if(A[k+1]==A[x]) k++;
urm[x]=k;
}
}
int main()
{
fin>>A>>B;
int n=strlen(A),m=strlen(B),i,k=-1;
urmat(n);
for(i=0;i<m;i++)
{
while(k>0&& A[k+1]!=B[i]) k=urm[k];
if(A[k+1]==B[i]) k++;
if(k==n-1)
{
h.push_back(i-n+1);
}
}
fout<<h.size()<<"\n";
i=1;
for(vector<int>::iterator it=h.begin();it!=h.end();it++)
{
fout<<*it<<" ";
if(i==999) break;
else i++;
}
}