Pagini recente » Cod sursa (job #3174177) | Cod sursa (job #2922511) | Cod sursa (job #2559127) | Cod sursa (job #691993) | Cod sursa (job #1757511)
#include <fstream>
#include <cstring>
#define DIM 2000001
using namespace std;
char t[DIM],b[DIM];
int s[DIM],p[DIM],i,j,n,m,nr,l;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int main (){
fin>>t+1;
n = strlen (t+1);
l = 0;
for (i=2;i<=n;i++){
while (l!=0 && t[i]!=t[l+1])
l = p[l];
if (t[i]==t[l+1])
l++;
p[i] = l;
}
fin>>b+1;
m = strlen (b+1);
l = 0;
for (i=1;i<=m;i++){
while (l!=0 && b[i]!=t[l+1])
l = p[l];
if (b[i] == t[l+1])
l++;
if (l == n){
s[++nr] = i-n;
l = p[l];
}
}
fout<<nr<<"\n";
if (nr <= 1000){
for (i=1;i<=nr;i++)
fout<<s[i]<<" ";
}
else{
nr = 1000;
for (i=1;i<=nr;i++)
fout<<s[i]<<" ";
}
return 0;
}
/*#include <fstream>
#include <cstring>
using namespace std;
int n,m,i,nr[1010],j,ap,ok,k;
char v[2000001],w[2000001],x;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int main (){
fin>>v;
fin>>w;
n = 0;
while ((v[n]>='0'&&v[n]<='9')||(v[n]>='a'&&v[n]<='z')||(v[n]>='A'&&v[n]<='Z'))
n++;
m = 0;
while ((w[m]>='0'&&w[m]<='9')||(w[m]>='a'&&w[m]<='z')||(w[m]>='A'&&w[m]<='Z'))
m++;
/*n = strlen (v);
m = strlen (w);
/* for (i=0;i<n;i++)
fout<<v[i];
fout<<"\n";
for (i=0;i<m;i++)
fout<<w[i];
*/
/* k = 0;
for (i=0;i<m;i++){
if (w[i] == v[k]){
k++;
if (k == n){
ap++;
if (ap <= 1000)
nr[ap] = i-n+1;
k = 0;
i -= n;
i++;
}
}
else
k = 0;
}
fout<<ap<<"\n";
if (ap <= 1000){
//ap = 1000;
for (i=1;i<=ap;i++)
fout<<nr[i]<<" ";
}
return 0;
}*/