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