Pagini recente » Cod sursa (job #1207026) | Cod sursa (job #813914) | Cod sursa (job #2354099) | Cod sursa (job #2404474) | Cod sursa (job #2556040)
#include <fstream>
#include <cstring>
#define NM 2000002
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,l;
int nr[NM],urm[NM];
string s1,s2;
void prefix(int n,string s1){
int i,j;
urm[0]=0; j=-1;
for(i=1;i<n;i++){
while(j>0&&s1[j+1]!=s1[i]) j=urm[j];
if(s1[j+1]==s1[i]) j++;
urm[i]=j;
}
}
int main()
{
f>>s1>>s2;
n=s1.size(); m=s2.size();
prefix(n,s1);
int i,j;
j=-1;
for(i=0;i<m&&l<1000;i++){
while(j>0&&s1[j+1]!=s2[i]) j=urm[j];
if(s1[j+1]==s2[i]) j++;
if(j==n-1&&l<1000){ nr[++l]=i-n+1;
j=urm[j];
}
}
g<<l<<'\n';
for(i=1;i<=l;i++)
g<<nr[i]<<' ';
return 0;
}