Pagini recente » Cod sursa (job #570214) | Cod sursa (job #2984709) | Cod sursa (job #3003036) | Cod sursa (job #636935) | Cod sursa (job #3195105)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define MAX 2000001
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[MAX], b[MAX];
int table[MAX];
vector <int> res;
int n, m, resContor;
void makeTable (){
int k = 0, i = 1;
while (i<n){
if (a[i] == a[k]){
++k;
table[i] = k;
++i;
}
else if (k != 0){
k = table[k-1];
}
else
++i;
}
}
void solve (){
int k = 0, i = 0;
while (i < m){
if (a[k] == b[i]){
++i;
++k;
if (k == n){
resContor++;
if (resContor <= 1000)
res.push_back(i - n);
k = table[k-1];
}
}
else if (b[i] != a[k]){
if (k == 0)
++i;
else
k = table[k-1];
}
}
}
void output (){
out << resContor << '\n';
for (auto x:res){
out << x << ' ';
}
}
int main (){
in >> a >> b;
n = strlen(a), m = strlen(b);
makeTable();
solve();
output();
return 0;
}