Pagini recente » Cod sursa (job #2122105) | Cod sursa (job #331501) | Cod sursa (job #583327) | Cod sursa (job #2299933) | Cod sursa (job #2847279)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
const int MAXN = 1000005;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
void KMP( const string &s, int lps[] ) {
int q = -1, n = s.length();
for ( int i = 1; i < n; ++i ) {
while ( q > 0 && s[q+1] != s[i] ) {
q = lps[q];
}
if ( s[q+1] == s[i] ) {
++q;
}
lps[i] = q+1;
}
}
int lps[MAXN];
vector<int> sol;
int main() {
string s, patt;
int q = -1;
fin >> patt >> s;
KMP(patt, lps);
for ( int i = 0; i < s.length(); ++i ) {
while ( q > 0 && patt[q+1] != s[i] ) {
q = lps[q];
}
if ( patt[q+1] == s[i] ) {
++q;
}
if ( q+1 == patt.length() ) {
if ( sol.size() < 1000 ) sol.push_back( i - patt.length() + 1 );
}
}
fout << sol.size() << "\n";
for ( int i = 0; i < sol.size(); ++i ) {
fout << sol[i] << " ";
}
fin.close();
fout.close();
return 0;
}