Pagini recente » Cod sursa (job #1507480) | Cod sursa (job #1165741) | Cod sursa (job #1284095) | Cod sursa (job #1796251) | Cod sursa (job #1509080)
#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=0,i;
for(i=2;i<=n;i++)
{
while(k>0 && A[k+1]!=A[i]) k=urm[k];
if(A[k+1]==A[i]) k++;
urm[i]=k;
}
}
int main()
{
fin>>(A+1)>>(B+1);
int n=strlen(A+1),m=strlen(B+1),i,k=0;
urmat(n);
for(i=1;i<=m;i++)
{
while(k>0&& A[k+1]!=B[i]) k=urm[k];
if(A[k+1]==B[i]) k++;
if(k==n)
{
h.push_back(i-n);
}
}
fout<<h.size()<<"\n";
i=1;
for(vector<int>::iterator it=h.begin();it!=h.end();it++)
{
fout<<*it<<" ";
if(i==1000) break;
i++;
}
}