太原本地网站,wordpress elegant,wordpress技术博客主题,北京室内设计公司排行榜Aho-Corasick算法简称AC算法#xff0c;也称为AC自动机(Aho-Corasick)算法#xff0c;1975年产生于贝尔实验室#xff08;The Bell Labs#xff09;#xff0c;是一种用于解决多模式字符串匹配的经典算法之一。 the Bell Lab
本文的运行效果#xff1a; AC算法以模式树…Aho-Corasick算法简称AC算法也称为AC自动机(Aho-Corasick)算法1975年产生于贝尔实验室The Bell Labs是一种用于解决多模式字符串匹配的经典算法之一。 the Bell Lab
本文的运行效果 AC算法以模式树字典树Trie、广度优先策略和KMP模式匹配算法为核心内容。 using System; using System.Collections; using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm { /// summary /// Aho_Corasick 算法 /// /summary public static partial class PatternSearch { private static int MAXS 512; private static int MAXC 26; private static int[] outt new int[MAXS]; private static int[] f new int[MAXS]; private static int[,] g new int[MAXS, MAXC]; private static int buildMatchingMachine(string[] arr, int k) { for (int i 0; i outt.Length; i) { outt[i] 0; } for (int i 0; i MAXS; i) { for (int j 0; j MAXC; j) { g[i, j] -1; } } int states 1; for (int i 0; i k; i) { string word arr[i]; int currentState 0; for (int j 0; j word.Length; j) { int ch word[j] - A; if (g[currentState, ch] -1) { g[currentState, ch] states; } currentState g[currentState, ch]; } outt[currentState] | (1 i); } for (int ch 0; ch MAXC; ch) { if (g[0, ch] -1) { g[0, ch] 0; } } for (int i 0; i MAXC; i) { f[i] 0; } Queueint q new Queueint(); for (int ch 0; ch MAXC; ch) { if (g[0, ch] ! 0) { f[g[0, ch]] 0; q.Enqueue(g[0, ch]); } } while (q.Count ! 0) { int state q.Peek(); q.Dequeue(); for (int ch 0; ch MAXC; ch) { if (g[state, ch] ! -1) { int failure f[state]; while (g[failure, ch] -1) { failure f[failure]; } failure g[failure, ch]; f[g[state, ch]] failure; outt[g[state, ch]] | outt[failure]; q.Enqueue(g[state, ch]); } } } return states; } private static int findNextState(int currentState, char nextInput) { int answer currentState; int ch nextInput - A; while (g[answer, ch] -1) { answer f[answer]; } return g[answer, ch]; } public static Listint Aho_Corasick_Search(string text, string pattern, int k 1) { Listint matchs new Listint(); string[] arr new string[1] { pattern }; buildMatchingMachine(arr, k); int currentState 0; for (int i 0; i text.Length; i) { currentState findNextState(currentState, text[i]); if (outt[currentState] 0) { continue; } for (int j 0; j k; j) { if ((outt[currentState] (1 j)) 0) { matchs.Add((i - arr[j].Length 1)); } } } return matchs; } } } POWER BY TRUFFER.CN
using System;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{/// summary/// Aho_Corasick 算法/// /summarypublic static partial class PatternSearch{private static int MAXS 512;private static int MAXC 26;private static int[] outt new int[MAXS];private static int[] f new int[MAXS];private static int[,] g new int[MAXS, MAXC];private static int buildMatchingMachine(string[] arr, int k){for (int i 0; i outt.Length; i){outt[i] 0;}for (int i 0; i MAXS; i){for (int j 0; j MAXC; j){g[i, j] -1;}}int states 1;for (int i 0; i k; i){string word arr[i];int currentState 0;for (int j 0; j word.Length; j){int ch word[j] - A;if (g[currentState, ch] -1){g[currentState, ch] states;}currentState g[currentState, ch];}outt[currentState] | (1 i);}for (int ch 0; ch MAXC; ch){if (g[0, ch] -1){g[0, ch] 0;}}for (int i 0; i MAXC; i){f[i] 0;}Queueint q new Queueint();for (int ch 0; ch MAXC; ch){if (g[0, ch] ! 0){f[g[0, ch]] 0;q.Enqueue(g[0, ch]);}}while (q.Count ! 0){int state q.Peek();q.Dequeue();for (int ch 0; ch MAXC; ch){if (g[state, ch] ! -1){int failure f[state];while (g[failure, ch] -1){failure f[failure];}failure g[failure, ch];f[g[state, ch]] failure;outt[g[state, ch]] | outt[failure];q.Enqueue(g[state, ch]);}}}return states;}private static int findNextState(int currentState, char nextInput){int answer currentState;int ch nextInput - A;while (g[answer, ch] -1){answer f[answer];}return g[answer, ch];}public static Listint Aho_Corasick_Search(string text, string pattern, int k 1){Listint matchs new Listint();string[] arr new string[1] { pattern };buildMatchingMachine(arr, k);int currentState 0;for (int i 0; i text.Length; i){currentState findNextState(currentState, text[i]);if (outt[currentState] 0){continue;}for (int j 0; j k; j){if ((outt[currentState] (1 j)) 0){matchs.Add((i - arr[j].Length 1));}}}return matchs;}}
}
