Pagini recente » Cod sursa (job #2677299) | Cod sursa (job #1909358) | Cod sursa (job #1691241) | Cod sursa (job #1584808) | Cod sursa (job #2222161)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMax = 2000003;
char x[NMax];
char y[NMax];
int pi[NMax];
int n;
vector<int> v;
void make_pi(char *x){
pi[0] = -1;
int k = -1;
int l = strlen(x);
for(int i = 1; i < l; ++i){
while(k > -1 && x[k + 1] != x[i])
k = pi[k];
if(x[k + 1] == x[i])
k++;
pi[i] = k;
}
}
void solve(char *x, char *y){
int len_x = strlen(x);
int len_y = strlen(y);
int k = -1;
for(int i = 0; i < len_y; ++i){
while(k > -1 && x[k + 1] != y[i])
k = pi[k];
if(x[k + 1] == y[i])
k++;
if(k == len_x - 1){
n++;
if(n <= 1000){
v.push_back(i - len_x + 1);
}
}
}
g << n << '\n';
for(int i = 0; i < v.size(); ++i){
g << v[i] << ' ';
}
}
int main()
{
f.getline(x,NMax);
f.getline(y,NMax);
make_pi(x);
solve(x,y);
return 0;
}