Advertisement
Guest User

Untitled

a guest
Dec 8th, 2016
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.90 KB | None | 0 0
  1. // Автор: Климчук Аня.
  2. // Описание: Поиск позиций вхождения шаблона в строке с помощью алгоритма Ахо-Корасика.
  3.  
  4. #include <iostream>
  5. #include <vector>
  6. #include <string>
  7. #include <map>
  8.  
  9. using namespace std;
  10.  
  11. // Вершина Бора.
  12. class CVertex{
  13. public:
  14. CVertex( int parent_ = -1, char symbol_ = '#' ){
  15. parent = parent_;
  16. symbol = symbol_;
  17. isTerminal = false;
  18. suffLink = -1;
  19. up = -1;
  20. };
  21. void AddSon( char symbol, int son ) {
  22. sons[symbol] = son;
  23. };
  24. int GetSon( char symbol ) const{
  25. map< char, int >::const_iterator it = sons.find( symbol );
  26. if( it != sons.end() )
  27. return it->second;
  28. return -1;
  29. }
  30. void AddGoLink( char symbol, int vertex ) {
  31. go[symbol] = vertex;
  32. }
  33. int GetGoLink( char symbol ) const{
  34. map< char, int >::const_iterator it = go.find( symbol );
  35. if( it != go.end() )
  36. return it->second;
  37. return -1;
  38. }
  39. int CountNeighbor() const{
  40. return sons.size();
  41. }
  42. void BeTerminal() {
  43. isTerminal = true;
  44. }
  45. bool IsTerminal() const{
  46. return isTerminal;
  47. }
  48. void AddPattern( int number ) {
  49. PatternNumbers.push_back( number );
  50. }
  51. void AddSuffLink( int suffLink_ ) {
  52. suffLink = suffLink_;
  53. }
  54. int GetSuffLink() const{
  55. return suffLink;
  56. }
  57. int GetParent() const{
  58. return parent;
  59. }
  60. char GetSymbol() const{
  61. return symbol;
  62. }
  63. void AddUp( int up_ ) {
  64. up = up_;
  65. }
  66. int GetUp() const{
  67. return up;
  68. }
  69. int CountPattern() const{
  70. return PatternNumbers.size();
  71. }
  72. int GetPattern( int i ) const{
  73. return PatternNumbers[i];
  74. }
  75. private:
  76. // Родитель, т.е. вершина, из которой пришли в данную.
  77. int parent;
  78. // Символ, по которому пришли в данную вершину.
  79. char symbol;
  80. // Индикатор, является ли данная вершина terminal.
  81. bool isTerminal;
  82. // Номера шаблонов, для которых данная вершина является terminal.
  83. vector<int> PatternNumbers;
  84. // map сыновей
  85. map< char, int > sons;
  86. // map переходов.
  87. map< char, int > go;
  88. // суффиксная ссылка
  89. int suffLink;
  90. // сжатая суффиксная ссылка
  91. int up;
  92. };
  93.  
  94. // Бор.
  95. class CBor{
  96. public:
  97. CBor() {
  98. allVertex.push_back( CVertex() );
  99. root = allVertex.size() - 1;
  100. }
  101. void AddPattern( string & patt )
  102. {
  103. patterns.push_back( patt );
  104. int current = root;
  105. for( int i = 0; i < patt.length(); ++i ) {
  106. int son = allVertex[current].GetSon( patt[i] );
  107. if( son != -1 ) {
  108. current = son;
  109. } else {
  110. allVertex.push_back( CVertex( current, patt[i] ) );
  111. int new_vertex = allVertex.size() - 1;
  112. allVertex[current].AddSon( patt[i], new_vertex );
  113. current = new_vertex;
  114. }
  115. }
  116. allVertex[current].BeTerminal();
  117. allVertex[current].AddPattern( patterns.size() - 1 );
  118. }
  119. // Суффиксная ссылка.
  120. // Возвращает вершину, в которой заканчивается максимальный несобственный суффикс.
  121. int GetSuffLink( int v );
  122. // Переход из вершины по символу.
  123. int GetLink( int v, char symbol );
  124. // Сжатая суффиксная ссылка.
  125. int GetUp( int v );
  126. int GetRoot() {
  127. return root;
  128. }
  129. int GetPatternSize( int i ) const{
  130. return patterns[i].size();
  131. }
  132. string GetPattern( int i ) const{
  133. return patterns[i];
  134. }
  135. void Check( int v, int i );
  136. void Find( string & text);
  137. private:
  138. int root;
  139. vector< CVertex > allVertex;
  140. vector< string > patterns;
  141. };
  142.  
  143. int CBor::GetSuffLink( int v )
  144. {
  145. CVertex * vertex = &allVertex[v];
  146. // Если на данный момент нет suffLink.
  147. if( vertex->GetSuffLink() == -1 ) {
  148. if( v == root || vertex->GetParent() == root ) {
  149. vertex->AddSuffLink( root );
  150. } else {
  151. vertex->AddSuffLink( GetLink( GetSuffLink( vertex->GetParent() ), vertex->GetSymbol()) );
  152. }
  153. }
  154. return vertex->GetSuffLink();
  155. }
  156.  
  157. int CBor::GetLink( int v, char symbol ) {
  158. CVertex * vertex = &allVertex[v];
  159. int link = vertex->GetGoLink( symbol );
  160. // Если из данной вершины уже есть переход по этому символу.
  161. if( link != -1 ) {
  162. return link;
  163. }
  164. link = vertex->GetSon( symbol);
  165. // Если у вершины есть ребенок с переходом по этому символу.
  166. if( link != -1 ) {
  167. vertex->AddGoLink( symbol, link );
  168. return link;
  169. }
  170. // Если данная вершина корень.
  171. if ( v == root) {
  172. vertex->AddGoLink( symbol, root );
  173. return root;
  174. }
  175. link = GetLink( GetSuffLink( v ), symbol );
  176. vertex->AddGoLink( symbol, link );
  177. return link;
  178. }
  179.  
  180. int CBor::GetUp( int v ) {
  181. CVertex * vertex = &allVertex[v];
  182. int link = vertex->GetUp();
  183. if( link != -1 ) {
  184. return link;
  185. }
  186. link = GetSuffLink( v );
  187. if( allVertex[link].IsTerminal() || link == root) {
  188. vertex->AddUp( link );
  189. return link;
  190. }
  191. link = GetUp( GetSuffLink( v ) );
  192. vertex->AddUp( link );
  193. return link;
  194. }
  195.  
  196. void CBor::Check( int v, int i ) {
  197. for( int u = v; u != 0; u = GetUp( u ) ) {
  198. CVertex * vertex = &allVertex[u];
  199. if( vertex->IsTerminal() ) {
  200. for( int j = 0; j < vertex->CountPattern(); ++j ) {
  201. cout << i - GetPatternSize( vertex->GetPattern( j ) ) + 1 << " ";
  202. cout << GetPattern( vertex->GetPattern( j ) ) << endl;
  203. }
  204. }
  205. }
  206. }
  207.  
  208. void CBor::Find( string & text ) {
  209. int current = GetRoot();
  210. for( int i = 0; i < text.length(); ++i ) {
  211. current = GetLink( current, text[i] );
  212. Check( current, i + 1 );
  213. }
  214. }
  215.  
  216. int main()
  217. {
  218. CBor b;
  219. /*string s = "he";
  220. b.AddPattern( s );
  221. s = "she";
  222. b.AddPattern( s );
  223. s = "his";
  224. b.AddPattern( s );
  225. s = "hers";
  226. b.AddPattern( s );
  227. */
  228. string s = "abc";
  229. b.AddPattern( s );
  230. s = "bcdc";
  231. b.AddPattern( s );
  232. s = "bcdc";
  233. b.AddPattern( s );
  234. s = "cccb";
  235. b.AddPattern( s );
  236. s = "bcdd";
  237. b.AddPattern( s );
  238. s = "bbbc";
  239. b.AddPattern( s );
  240. s = "abcdcbcddbbbcccbbbcccbb";
  241. b.Find( s );
  242. return 0;
  243. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement