Pagini recente » Cod sursa (job #284210) | Cod sursa (job #2516761) | Cod sursa (job #1492010) | Cod sursa (job #2157408) | 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;
}