Pagini recente » Cod sursa (job #446826) | Cod sursa (job #1786470) | Cod sursa (job #2697969) | Cod sursa (job #1034077) | Cod sursa (job #3285538)
#include <bits/stdc++.h>
#define DIM 20000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int lps[DIM];
int n, m, i;
vector <int> sol;
void Build_LPS(){
int j = 0;
for(int i=1;i<n;i++){
while(j > 0 && a[i] != a[j])
j = lps[j - 1];
if(a[i] == a[j])
++j;
lps[i] = j;
}
}
void Compute_Matches(){
int j = 0;
for(int 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){
sol.push_back(i - n + 1);
j = lps[j - 1];
}
}
}
int32_t main(){
fin >> a >> b;
n = a.size();
m = b.size();
Build_LPS();
Compute_Matches();
fout << sol.size() << "\n";
for(int i=0;i<min(1000, (int)sol.size());i++)
fout << sol[i] << " ";
}