Pagini recente » Cod sursa (job #2470011) | Cod sursa (job #386561) | Cod sursa (job #820699) | Cod sursa (job #138284) | Cod sursa (job #1968483)
#include<fstream>
#include<cstring>
#include<vector>
#define DIM 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2 * DIM], s1[DIM];
int n, st, dr, z[DIM], lg;
vector<int> sol;
int main(){
fin >> s;
lg = strlen( s );
fin >> s1;
strncat( s, s1, sizeof(s1) );
n = strlen( s ) - 1;
z[0] = 0;
st = dr = 0;
for( int i = 1; i <= n; i++ ){
if( i > dr ){
int poz = 0;
while( s[poz] == s[i + poz] && poz <= n ){
poz++;
}
st = i;
dr = poz + st - 1;
z[i] = poz;
}else{
if( z[i - st] < dr - i + 1 ){
z[i] = z[i - st];
}else{
z[i] = dr - i + 1;
int poz = z[i];
int nr = 0;
while( s[poz] == s[i + poz] && poz <= n ){
nr++;
poz++;
}
z[i] += nr;
st = i;
dr = i + z[i] - 1;
}
}
if( sol.size() >= 1000 )
break;
if( i >= lg && z[i] >= lg ){
sol.push_back( i - lg );
}
}
fout << sol.size() << "\n";
for( int i = 0; i < sol.size(); i++ ){
fout << sol[i] << " ";
}
return 0;
}