Pagini recente » Cod sursa (job #2977776) | Cod sursa (job #3166761) | Cod sursa (job #2991305) | Cod sursa (job #2855365) | Cod sursa (job #3261068)
#include <bits/stdc++.h>
#define DIM 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector <int> sol;
int pi[DIM];
int i, j;
string a, b;
void Build_LPS(){
for(i=1;i<a.size();i++){
while(j > 0 && a[i] != a[j])
j = pi[j - 1];
if(a[i] == a[j])
++j;
pi[i] = j;
}
}
void Compute_Matches(){
j = 0;
for(i=0;i<b.size();i++){
while(j > 0 && b[i] != a[j])
j = pi[j - 1];
if(b[i] == a[j])
++j;
if(j == a.size()){
sol.push_back(i - a.size() + 1);
j = pi[j - 1];
}
}
}
int main(){
fin >> a >> b;
Build_LPS();
Compute_Matches();
fout << sol.size() << "\n";
for(i=0;i<min(int(sol.size()), 1000);i++)
fout << sol[i] << " ";
}