# 小米 2018 校招算法工程师编程之字符串匹配

··434 words·3 mins·

``````#include <bits/stdc++.h>
using namespace std;

string text, pattern;
// posInPattern mean the next search character in pattern
// posInText means the next pos the search start
int dfs(int posInPattern, int posInText){
if (posInPattern == (int)pattern.size()){
return posInText-1;
}

int endID = -1;
for (int i = posInText; i != (int)text.size(); ++i){
if (text[i] == pattern[posInPattern]){
endID = dfs(posInPattern+1, i+1);
break;
}
}
return endID;
}

int main(){
cin >> text >> pattern;

int lenText = (int)text.size();
int lenPattern = (int)pattern.size();

vector<pair<int, int>> records;
for (int i = 0; i <= lenText-lenPattern; ++i){
if (text[i] == pattern[0]){
int end = dfs(1, i+1);
if (end != -1){
records.push_back(make_pair(i, end));
}// if no matching substring are found starting from current
//position, then no substring can be found after this position.
else{
break;
}
}
}

if (records.empty()) {// if no matching substring is found
cout << "-1 -1\n";
}
else{ // if mathcing substring is found, then select the shortest one.
int begin = records[0].first, end = records[0].second;
for (auto it = records.begin()+1; it != records.end(); ++it){
if (it->second - it->first < end - begin){
begin = it->first;
end = it->second;
}
}
cout << begin << " " << end << '\n';
}

return 0;
}
``````

``````#include <bits/stdc++.h>
using namespace std;
int main(){
string text, pattern;
cin >> text >> pattern;
int lenText = (int)text.size();
int lenPattern = (int)pattern.size();
vector<pair<int, int>> record;

for (int i = 0; i <= lenText-lenPattern; ++i){
if (text[i] != pattern[0]){
continue;
}
else{
int j = i+1; // next search position in text
int k = 1; // next search character in pattern
while (j < lenText && k < lenPattern){
if (text[j] == pattern[k]){
++k;
}
++j;
}
// if we found the string
if (k == lenPattern){
record.push_back(make_pair(i, j-1));
}
else{ break;} // we cann't find any string after, so break
}
}
if (records.empty()) {// if no matching substring is found
cout << "-1 -1\n";
}
else{ // if mathcing substring is found, then select the shortest one.
int begin = records[0].first, end = records[0].second;
for (auto it = records.begin()+1; it != records.end(); ++it){
if (it->second - it->first < end - begin){
begin = it->first;
end = it->second;
}
}
cout << begin << " " << end << '\n';
}

return 0;
}
``````

(全文完)

## Related

··225 words·2 mins

··504 words·3 mins
When Does the Stability of Sorting Algorithms Matter?
··363 words·2 mins