Pagini recente » Cod sursa (job #2754577) | Cod sursa (job #496319) | Cod sursa (job #636015) | Cod sursa (job #129165) | Cod sursa (job #2438536)
#include <iostream>
#include <fstream>
using namespace std;
#include <string>
#include <vector>
void prefix(std::vector<int> &pi, string &A){
int n = A.size();
int k = 0, i;
pi.resize(n);
for( i = 1, pi[0] = 0;i < n;i++){
while(k && (A[k] != A[i])){
k = pi[k-1];
}
if(A[k] == A[i]){
++k;
}
pi[i] = k;
}
}
std::vector<int> match(std::vector<int> &pi, string &A, string &B, int &N){
int n = A.size();
int m = B.size();
int q = 0;
std::vector<int> pozition;
for (int i = 0; i < m; i++){
while(q && A[q] != B[i]){
q = pi[q-1];
}
if(A[q] == B[i]){
q++;
}
if(q == n && ++N <= 1000){
pozition.push_back(i-n+1);
}
}
return pozition;
}
int main(){
string A;
string B;
std::vector<int> pi;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int N = 0;
fin >> A;
fin >> B;
prefix(pi, A);
std::vector<int> poz = match(pi, A, B, N);
fout << N << '\n';
for (int i = 0; i < poz.size(); i++){
fout << poz[i] <<" ";
}
return 0;
}