Pagini recente » Cod sursa (job #2019114) | Istoria paginii runda/probleme_oji/clasament | Cod sursa (job #1569940) | Cod sursa (job #2233766) | Cod sursa (job #1291544)
#include <vector>
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int maxn = 2000005;
char pattern[maxn], text[maxn];
int n, m, pi[maxn];
int main() {
fin >> pattern + 1 >> text + 1;
n = strlen(pattern + 1);
m = strlen(text + 1);
int k = 0;
for(int i = 2 ; i <= n ; ++ i) {
while(k > 0 && pattern[i] != pattern[k + 1])
k = pi[k];
if(pattern[i] == pattern[k + 1])
++ k;
pi[i] = k;
}
vector <int> matches;
k = 0;
for(int i = 1 ; i <= m ; ++ i) {
while(k > 0 && text[i] != pattern[k + 1])
k = pi[k];
if(text[i] == pattern[k + 1])
++ k;
if(k == n)
matches.push_back(i - k);
}
fout << matches.size() << '\n';
for(int i = 0 ; i < min(1000, int(matches.size())) ; ++ i)
fout << matches[i] << ' ';
}