Pagini recente » Cod sursa (job #2724960) | Cod sursa (job #2229519) | Cod sursa (job #3002669) | Cod sursa (job #1378627) | Cod sursa (job #1964617)
#include<fstream>
#include<cstring>
#define DIM 2000005
using namespace std;
int n, m, st, dr, poz, i, j, nr;
char s[2 * DIM], a[DIM];
int p[2 * DIM], sol[1005];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main(){
fin>> s + 1;
m = strlen(s + 1);
fin>> a + 1;
n = strlen(a + 1);
for(i = m + 1; i <= n + m; i++){
s[i] = a[i - m];
}
n += m;
for(i = 2; i <= n; i++){
if(dr < i){
j = 1;
while(j <= n && s[j] == s[i + j - 1]){
j++;
}
j--;
p[i] = j;
dr = i + j - 1;
st = i;
if(p[i] >= m && i > m){
nr++;
if(nr <= 1000){
sol[nr] = i;
}
}
continue;
}
poz = i - st + 1;
if(poz + p[poz] - 1 < dr - st + 1){
p[i] = p[poz];
}
else{
j = dr - st + 1;
while(j <= n && s[j] == s[i + j - 1]){
j++;
}
j--;
p[i] = j;
}
if(i + p[i] - 1 > dr){
st = i;
dr = i + p[i] - 1;
}
if(p[i] >= m && i > m){
nr++;
if(nr <= 1000){
sol[nr] = i;
}
}
}
fout<< nr <<"\n";
for(i = 1; i <= min(1000, nr); i++){
fout<< sol[i] - m - 1 <<" ";
}
return 0;
}