Pagini recente » Istoria paginii runda/asa_de_vacanta_ix/clasament | Cod sursa (job #3293093) | Cod sursa (job #2765922) | Cod sursa (job #808786) | Cod sursa (job #2770475)
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
const int MAXN = 2000005;
int lcp[MAXN];
vector<int> res;
void getlcp( string s ) {
int n = s.length(), l = 0, r = 0;
for ( int i = 1; i < n; ++i ) {
if ( i <= r ) {
lcp[i] = min( r - i + 1, lcp[i - l] );
}
while ( i + lcp[i] < n && s[lcp[i]] == s[i + lcp[i]] ) {
++lcp[i];
}
if ( i + lcp[i] - 1 > r ) {
l = i;
r = i + lcp[i] - 1;
}
}
}
int main() {
string s, t;
int m;
fin >> s >> t;
m = s.length();
s = s + '#' + t;
getlcp( s );
for ( int i = 1; i < s.length(); ++i ) {
if ( lcp[i] == m ) {
res.push_back( i - m - 1 );
}
}
int sz = min( (int)res.size(), 1000 );
fout << sz << "\n";
for ( int i = 0; i < sz; ++i ) {
fout << res[i] << " ";
}
fin.close();
fout.close();
return 0;
}