本文概述
- C ++
- C
- Java
- C#

文章图片

文章图片
上面的图代表ACACAGA模式的图形和表格表示。
算法:
1)填写第一行。除pat [0]字符的条目外, 第一行中的所有条目始终为0。对于pat [0]字符, 我们总是需要进入状态1。
2)将lps初始化为0。第一个索引的lps始终为0。
3)对索引i = 1到M的行执行以下操作(M是模式的长度)
…..a)从索引等于lps的行中复制条目。
…..b)将pat [i]字符的条目更新为i + 1。
…..c)更新lps" lps = TF [lps] [pat [i]]", 其中TF是正在构建的2D数组。
以下是上述算法的C / C ++实现。
实现
C ++
#include <
bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256/* This function builds the TF table
which represents Finite Automata for a
given pattern */
void computeTransFun( char * pat, int M, int TF[][NO_OF_CHARS])
{
int i, lps = 0, x;
// Fill entries in first row
for (x = 0;
x <
NO_OF_CHARS;
x++)
TF[0][x] = 0;
TF[0][pat[0]] = 1;
// Fill entries in other rows
for (i = 1;
i <
= M;
i++) {
// Copy values from row at index lps
for (x = 0;
x <
NO_OF_CHARS;
x++)
TF[i][x] = TF[lps][x];
// Update the entry corresponding to this character
TF[i][pat[i]] = i + 1;
// Update lps for next row to be filled
if (i <
M)
lps = TF[lps][pat[i]];
}
}/* Prints all occurrences of pat in txt */
void search( char pat[], char txt[])
{
int M = strlen (pat);
int N = strlen (txt);
int TF[M + 1][NO_OF_CHARS];
computeTransFun(pat, M, TF);
// process text over FA.
int i, j = 0;
for (i = 0;
i <
N;
i++) {
j = TF[j][txt[i]];
if (j == M) {
cout <
<
"pattern found at index " <
<
i - M + 1 <
<
endl;
}
}
}/* Driver code */
int main()
{
char txt[] = "GEEKS FOR GEEKS" ;
char pat[] = "GEEKS" ;
search(pat, txt);
return 0;
}// This is code is contributed by rathbhupendra
C
#include <
stdio.h>
#include <
string.h>
#define NO_OF_CHARS 256/* This function builds the TF table which represents Finite Automata for a
given pattern*/
void computeTransFun( char * pat, int M, int TF[][NO_OF_CHARS])
{
int i, lps = 0, x;
// Fill entries in first row
for (x = 0;
x <
NO_OF_CHARS;
x++)
TF[0][x] = 0;
TF[0][pat[0]] = 1;
// Fill entries in other rows
for (i = 1;
i <
= M;
i++) {
// Copy values from row at index lps
for (x = 0;
x <
NO_OF_CHARS;
x++)
TF[i][x] = TF[lps][x];
// Update the entry corresponding to this character
TF[i][pat[i]] = i + 1;
// Update lps for next row to be filled
if (i <
M)
lps = TF[lps][pat[i]];
}
}/* Prints all occurrences of pat in txt */
void search( char * pat, char * txt)
{
int M = strlen (pat);
int N = strlen (txt);
int TF[M + 1][NO_OF_CHARS];
computeTransFun(pat, M, TF);
// process text over FA.
int i, j = 0;
for (i = 0;
i <
N;
i++) {
j = TF[j][txt[i]];
if (j == M) {
printf ( "\n pattern found at index %d" , i - M + 1);
}
}
}/* Driver program to test above function */
int main()
{
char * txt = "GEEKS FOR GEEKS" ;
char * pat = "GEEKS" ;
search(pat, txt);
getchar ();
return 0;
}
Java
/* A Java program to answer queries to check whether
the substrings are palindrome or not efficiently */class GFG
{static int NO_OF_CHARS = 256 ;
/* This function builds the TF table
which represents Finite Automata for a
given pattern */
static void computeTransFun( char [] pat, int M, int TF[][])
{
int i, lps = 0 , x;
// Fill entries in first row
for (x = 0 ;
x <
NO_OF_CHARS;
x++)
{
TF[ 0 ][x] = 0 ;
}
TF[ 0 ][pat[ 0 ]] = 1 ;
// Fill entries in other rows
for (i = 1 ;
i <
M;
i++)
{
// Copy values from row at index lps
for (x = 0 ;
x <
NO_OF_CHARS;
x++)
{
TF[i][x] = TF[lps][x];
}// Update the entry corresponding to this character
TF[i][pat[i]] = i + 1 ;
// Update lps for next row to be filled
if (i <
M)
{
lps = TF[lps][pat[i]];
}
}
}/* Prints all occurrences of pat in txt */
static void search( char pat[], char txt[])
{
int M = pat.length;
int N = txt.length;
int [][] TF = new int [M + 1 ][NO_OF_CHARS];
computeTransFun(pat, M, TF);
// process text over FA.
int i, j = 0 ;
for (i = 0 ;
i <
N;
i++)
{
j = TF[j][txt[i]];
if (j == M)
{
System.out.println( "pattern found at index " +
(i - M + 1 ));
}
}
}/* Driver code */
public static void main(String[] args)
{
char txt[] = "GEEKS FOR GEEKS" .toCharArray();
char pat[] = "GEEKS" .toCharArray();
search(pat, txt);
}
}// This code is contributed by Princi Singh
C#
/* A C# program to answer queries to check whether
the substrings are palindrome or not efficiently */
using System;
class GFG
{static int NO_OF_CHARS = 256;
/* This function builds the TF table
which represents Finite Automata for a
given pattern */
static void computeTransFun( char [] pat, int M, int [, ]TF)
{
int i, lps = 0, x;
// Fill entries in first row
for (x = 0;
x <
NO_OF_CHARS;
x++)
{
TF[0, x] = 0;
}
TF[0, pat[0]] = 1;
// Fill entries in other rows
for (i = 1;
i <
M;
i++)
{
// Copy values from row at index lps
for (x = 0;
x <
NO_OF_CHARS;
x++)
{
TF[i, x] = TF[lps, x];
}// Update the entry corresponding to this character
TF[i, pat[i]] = i + 1;
// Update lps for next row to be filled
if (i <
M)
{
lps = TF[lps, pat[i]];
}
}
}/* Prints all occurrences of pat in txt */
static void search( char []pat, char []txt)
{
int M = pat.Length;
int N = txt.Length;
int [, ] TF = new int [M + 1, NO_OF_CHARS];
computeTransFun(pat, M, TF);
// process text over FA.
int i, j = 0;
for (i = 0;
i <
N;
i++)
{
j = TF[j, txt[i]];
if (j == M)
{
Console.WriteLine( "pattern found at index " +
(i - M + 1));
}
}
}/* Driver code */
public static void Main(String[] args)
{
char []txt = "GEEKS FOR GEEKS" .ToCharArray();
char []pat = "GEEKS" .ToCharArray();
search(pat, txt);
}
}// This code is contributed by Rajput-Ji
输出如下:
pattern found at index 0 pattern found at index 10
FA构造的时间复杂度为O(M * NO_OF_CHARS)。搜索代码与以前的帖子时间复杂度为O(n)。
【模式搜索S6(有限自动机的有效构造)介绍和代码实现】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- 3D测量法详细介绍和示例指南
- PHP fputcsv()函数用法示例
- python3语句,缩进和注释 – Python3教程
- PHP Ds PriorityQueue count()函数用法介绍
- 如何交换给定整数中的两位()
- Python OpenCV cv2.line()方法用法介绍
- 高级算法设计(打印N皇后问题中的所有解决方案)
- 如何在Windows中安装Jupyter Notebook()
- C#方法介绍和用法详细指南