Pagini recente » Cod sursa (job #285634) | Cod sursa (job #1839569) | Cod sursa (job #1512120) | Cod sursa (job #1191259) | Cod sursa (job #1198241)
#include <fstream>
#include <cstring>
using namespace std;
const int N = 1 + 2e6, AnsSize = 1e3;
char text[N], pattern[N];
int Z[N], match[N], ans[N];
void runSequence(char text[], char pattern[], int Z[], int match[]){
int best = 0;
for (int i = 1 ; text[i] ; i++){
if ( i < best + match[best] )
match[i] = min( best + match[best] - i, Z[i - best + 1] );
while ( text[ i + match[i] ] && pattern[ match[i] + 1 ] == text[ i + match[i] ] )
match[i]++;
if (best + match[best] < i + match[i])
best = i;
}
}
void strmatch(char text[], char pattern[], int match[]){
runSequence(pattern, pattern, Z, Z);
runSequence(text, pattern, Z, match);
}
int main(){
ifstream in("strmatch.in");
in >> (pattern + 1) >> (text + 1);
in.close();
strmatch(text, pattern, match);
int n = strlen(pattern + 1);
for (int i = 1 ; text[i] ; i++)
if ( match[i] == n )
ans[ ++ans[0] ] = i;
ofstream out("strmatch.out");
out << ans[0] << '\n';
for (int i = 1 ; i <= ans[0] && i <= AnsSize ; i++)
out << ans[i] - 1 << ' ';
out << '\n';
out.close();
return 0;
}