Pagini recente » Cod sursa (job #2277341) | Cod sursa (job #2379068) | Cod sursa (job #1151598) | Cod sursa (job #1824543) | Cod sursa (job #2514876)
#include <fstream>
#include <cstring>
#define LMAX 200005
#define SOLMAX 1005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[LMAX], b[LMAX];
int p[LMAX];
int sol[SOLMAX], nr;
int m, n;
void formprefix(){
p[1]=0;
int i=0;
for(int j=2; j<=m; j++){
while(i>0 && a[i+1]!=a[j])
i=p[i];
if(a[i+1] == a[j])
++i;
p[j] = i;
}
}
void cautCuvant(){
int k=0;
for(int i=1; i<=n; i++){
while(k && a[k+1]!=b[i])
k=p[k];
if(a[k+1] == b[i])
++k;
if(k == m){
nr++;
if(nr<=1000)
sol[nr] = i-m;
}
}
}
void afisprefix(){
for(int i=1; i<=m; i++)
g<<p[i]<<" ";
}
void afisSol(){
g<<nr<<'\n';
for(int i=1;i<=nr;i++)
g<<sol[i]<<' ';
}
int main()
{
f.getline(a+1, LMAX);
f.getline(b+1, LMAX);
m = strlen(a+1);
n = strlen(b+1);
formprefix();
//afisprefix();
cautCuvant();
afisSol();
return 0;
}