Pagini recente » Cod sursa (job #272421) | Cod sursa (job #1769821) | Cod sursa (job #2275013) | Cod sursa (job #2820831) | Cod sursa (job #1799485)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream be("strmatch.in");
ofstream ki("strmatch.out");
int n,m,nr,pi[2000000],k,i,p[2000000];
char a[2000001],b[20000001];
void set_pi(){
k = 0; pi[0] = k;
for(i = 1; i <= m; i++){
while(k>0 and a[i] != a[k])
k = pi[k-1];
if(a[i] == a[k])
k = k + 1;
pi[i] = k;
}
}
int main()
{
be >> a >> b;
n = strlen(b) - 1; m = strlen(a) - 1;
if(m == 0){
nr = 0;
for(i = 0; i <= n; ++i){
if(b[i] == a[0]) {
nr = nr + 1;
p[nr] = i;
}
}
}
else {
set_pi();
k = 0; nr = 0;
for(i = 0; i <= n; ++i){
while(k > 0 && b[i] !=a[k]){
k = pi[k-1];
}
if(b[i] == a[k]) k = k + 1;
if(k == m+1){
nr = nr + 1;
p[nr] = i - m;
k= pi[k-1];
}
}
}
ki << nr << "\n";
if(nr > 1000) nr = 1000;
for(i = 1; i <= nr; i++) ki << p[i] << " ";
return 0;
}