Pagini recente » Cod sursa (job #1982508) | Cod sursa (job #2538885) | Cod sursa (job #2335805) | Cod sursa (job #196980) | Cod sursa (job #2984007)
#include<bits/stdc++.h>
#define DIM 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int lps[DIM], ans[DIM];
int n, m, i, j, k;
string a, b;
void Compute_LPS(){
for(i=1;i<n;i++){
while(j > 0 && a[i] != a[j])
j = lps[j - 1];
if(a[j] == a[i])
j++;
lps[i] = j;
}
}
void KMP(){
Compute_LPS();
j = 0;
for(i=0;i<m;i++){
while(j > 0 && a[j] != b[i])
j = lps[j - 1];
if(a[j] == b[i])
j++;
if(j == n){
ans[++k] = i - n + 1;
j = lps[j - 1];
}
}
}
int main(){
fin >> a >> b;
n = a.size();
m = b.size();
KMP();
fout << k << "\n";
for(i=1;i<=min(1000, k);i++)
fout << ans[i] << " ";
}