Pagini recente » Cod sursa (job #471645) | Cod sursa (job #6874) | Cod sursa (job #3294552) | Cod sursa (job #2757519) | Cod sursa (job #3297464)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<int> kmp( const std::string &str ) {
std::vector<int> lcp(str.size(), 0);
for( int i = 1; i < (int)str.size(); i++ ){
int tactu = lcp[i - 1];
while( tactu && str[tactu] != str[i] )
tactu = lcp[tactu - 1];
if( str[tactu] == str[i] )
lcp[i] = 1 + tactu;
else
lcp[i] = 0;
}
return lcp;
}
int main() {
std::ifstream fin( "strmatch.in" );
std::ofstream fout( "strmatch.out" );
std::string text;
std::string pat;
fin >> pat >> text;
std::string totul = pat + '|' + text;
std::vector<int> mata = kmp( totul );
std::vector<int> out;
for( int i = 0; i < (int)text.size(); i++ )
if( mata[(int)pat.size() + 1 + i] >= (int)pat.size() )
out.push_back( i + 1 - (int)pat.size() );
fout << out.size() << '\n';
if( out.size() > 1000 )
out.resize( 1000 );
for( int x : out ) fout << x << ' '; fout << '\n';
return 0;
}