Pagini recente » Cod sursa (job #1254859) | Cod sursa (job #1249365) | Cod sursa (job #3257021) | Cod sursa (job #98370) | Cod sursa (job #3295452)
#include <fstream>
#include <vector>
using namespace std;
vector <int> ras;
int z[4000005];
int main(){
int i, target, best;
string a, b;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
fin >> a >> b;
target = a.size();
a += '$';
a += b;
best = 0;
for( i = 1; i < a.size(); i++ ){
if( i <= best + z[best] - 1 ){
z[i] = min( z[i - best], best + z[best] - i );
}
while( i + z[i] < a.size() && a[z[i]] == a[i + z[i]] ){
z[i]++;
}
if( i + z[i] > best + z[best] ){
best = i;
}
if( z[i] == target ){
ras.push_back( i - target - 1 );
}
}
fout << ras.size() << '\n';
for( i = 0; i < min( ( int )ras.size(), 1000 ); i++ ){
fout << ras[i] << ' ';
}
return 0;
}