Pagini recente » Cod sursa (job #2903266) | Cod sursa (job #405878) | Cod sursa (job #3187323) | Cod sursa (job #300445) | Cod sursa (job #1198240)
#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 + 1, 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;
}