Pagini recente » Cod sursa (job #917568) | Cod sursa (job #2239898) | Cod sursa (job #2007123) | Cod sursa (job #605639) | Cod sursa (job #1987795)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std ;
const int MAX = 2e6 ;
ifstream cin ("strmatch.in") ;
ofstream cout ("strmatch.out") ;
char sir [MAX * 2 + 15] ;
int main() {
cin >> (sir + 1) ;
int l = strlen (sir + 1) ;
int keep = l ;
sir [l + 1] = '#' ;
cin >> (sir + l + 2) ;
l = strlen (sir + 1) ;
vector <int> p (l + 1) ;
vector <int> positions ;
int number = 0 ;
for (int i = 2 ; i <= l ; ++ i) {
int best = p [i - 1] ;
while (best != 0 and sir [best + 1] != sir [i]) {
best = p [best] ;
}
if (sir [best + 1] == sir [i]) {
p[i] = best + 1;
if (p [i] == keep) {
if (number > 1000) ++ number ;
else {
++ number ;
positions.push_back(i - 2 * keep - 1) ;
}
}
}
}
cout << number << '\n' ;
for (auto x : positions) {
cout << x << ' ' ;
}
return 0;
}