Pagini recente » Cod sursa (job #2603027) | Cod sursa (job #367820) | Cod sursa (job #3250622) | Cod sursa (job #525357) | Cod sursa (job #2905464)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 2e6;
ifstream fin( "strmatch.in" );
ofstream fout( "strmatch.out" );
int z[2*NMAX+1];
vector <int> poz;
int main() {
int l, r, i, x;
string str, pattern, s;
fin >> pattern >> str;
s = "";
s += pattern;
s += '#';
s += str;
l = r = 0;
for( i = 0; i < s.size(); i++ ) {
if( i <= r ) {
if( z[i-l] < r - i + 1 )
z[i] = z[i-l];
else {
l = i;
r++;
while( r < s.size() && s[r] == s[r-l] )
r++;
r--;
z[i] = r - i + 1;
}
}
else {
l = r = i;
while( r < s.size() && s[r] == s[r-l] )
r++;
r--;
z[i] = r - l + 1;
}
}
for( i = pattern.size(); i < s.size(); i++ ) {
if( z[i] == pattern.size() )
poz.push_back( i );
}
fout << poz.size() << "\n";
x = 0;
for( auto it = poz.begin(); it != poz.end() && x < 1000; it++ ) {
fout << *it - pattern.size() - 1 << " ";
x++;
}
return 0;
}