C++算法

### C++ 中的 KMP 和 A* 算法简介 #### KMP 字符串匹配算法 KMP（Knuth-Morris-Pratt）字符串匹配算法是一种高效的模式匹配算法，在最坏情况下时间复杂度为 O(n+m)，其中 n 是主串长度，m 是模式串长度。该算法通过预计算部分匹配表(next数组)来避免不必要的回溯操作。 下面是一个完整的 KMP 实现示例： ```cpp #include <iostream> #include <string> using namespace std; int *renext(const string& pattern){ int length = pattern.size(); int *nextArr = new int[length]; nextArr[0] = -1; int k = -1; for(int i=1;i<length;++i){ while(k>-1 && pattern[k+1]!=pattern[i]) k = nextArr[k]; if(pattern[k+1]==pattern[i]){ ++k; } nextArr[i]=k; } return nextArr; } bool KMPSearch(const string& text, const string& pattern){ int m=text.length(),n=pattern.length(); int *nextArr = renext(pattern); int q=-1; for(int i=0;i<m&&q<n;++i){ while(q>-1 && pattern[q+1]!=text[i]) q=nextArr[q]; if(pattern[q+1]==text[i]) ++q; if(q==n-1){ delete[] nextArr; return true; } } delete[] nextArr; return false; } ``` 此版本修正了原始代码中的错误并增加了 `renext` 函数用于构建 next 数组[^1]。 #### A* 路径规划算法 A*(A-star) 是一种广泛应用于路径寻找和图遍历的人工智能技术。它结合了 Dijkstra 的最优性和贪心最佳首优搜索的优点。其核心在于维护一个开放列表(open list)存储待评估节点以及闭合列表(closed list)记录已访问过的节点。 以下是简化版 A* 算法框架: ```cpp struct Node { pair<int,int> pos; //位置坐标(x,y) double gScore,hScore,fScore; //g代价 h估计 f总分 }; double heuristic(Node a,Node b){ /*...*/} //定义启发式距离估算函数 void astar_search(vector<vector<Node>>& grid, Node start, Node goal){ priority_queue<pair<double,Node>> openList; unordered_set<Node*> closedSet; auto compare=[&](const pair<double,Node>& lhs,const pair<double,Node>& rhs)->bool{ return lhs.first > rhs.first; }; make_heap(openList.begin(),openList.end(),compare); push_heap(openList,start.fScore,{start}); while(!empty(openList)){ pop_heap(openList,compare); Node current=openList.top().second; if(current.pos==goal.pos){ break; } addNeighborsToOpenList(grid,current,closedSet,&openList,&heuristic,goal); insertIntoClosedSet(&closedSet,&current); } } ``` 上述伪代码展示了基本结构，实际应用时需自定义网格模型、邻居添加逻辑及状态管理等功能[^2].