问题—— 接受不以子字符串“THE”结尾的字符串。检查给定字符串是否以“the”结尾。字符串末尾避免的“The”的不同形式有：
null
"THE", "ThE", "THe", "tHE", "thE", "The", "tHe" and "the"
不接受以上述任何形式的“the”结尾的所有字符串。
Determinitis是字符串的有限自动机（DFA），不以“THE”结尾- 此dfa中的初始和起始状态为Qo
![图片[1]-不以“THE”结尾的字符串的DFA-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_22-2.jpg)
项目中使用的方法—— 在这个程序中，考虑4个状态是0, 1, 2和3。现在让我们取一个名为DFA的变量，它的初始值为0。无论何时发生任何转换，它都会用与新状态关联的数字更新DFA的值。
例子： 如果发生从状态0到状态1的转换，则DFA的值将更新为1。如果发生从状态2到状态3的转换，则dfa的值将更新为3。这样，在整个字符串上应用这个算法，如果最后达到状态0、1或2，那么我们的字符串将被接受，否则不会被接受。
Input : XYzabCtheOutput : NOT ACCEPTEDInput : ThemaliktthOutput : ACCEPTED
C++
// C++ program to implement DFS that accepts // all string that do not end with "THE" #include <iostream> using namespace std; // dfa tells the number associated // with the present state int dfa = 0; // This function is for // the starting state (zeroth) of DFA void start( char c) { // On receiving 'T' or 't' goto // first state (1) if (c == 't' || c == 'T' ) dfa = 1; } // This function is for the first state of DFA void state1( char c) { // On receiving 'T' or 't' goto // first state (1) if (c == 't' || c == 'T' ) dfa = 1; // On receiving 'H' or 'h' // goto second state (2) else if (c == 'h' || c == 'H' ) dfa = 2; // Else goto starting state (0) else dfa = 0; } // This function is for the second state of DFA void state2( char c) { // On receiving 'E' or 'e' goto third state (3) // else goto starting state (0) if (c == 'e' || c == 'E' ) dfa = 3; else if (c == 't' || c == 'T' ) dfa = 1; else dfa = 0; } // This function is for the third state of DFA void state3( char c) { // On receiving 'T' or 't' goto first state (1) // else goto starting state (0) if (c == 't' || c == 'T' ) dfa = 1; else dfa = 0; } bool isAccepted(string str) { // Store length of string int len = str.length(); for ( int i = 0; i < len; i++) { if (dfa == 0) start(str[i]); else if (dfa == 1) state1(str[i]); else if (dfa == 2) state2(str[i]); else state3(str[i]); } return (dfa != 3); } // Driver code int main() { string str = "forTHEgeeks" ; if (isAccepted(str) == true ) cout << "ACCEPTED" ; else cout << "NOT ACCEPTED" ; return 0; } // This code is contributed by ShubhamSingh10 |
C
// C program to implement DFS that accepts // all string that do not end with "THE" #include <stdio.h> #include <string.h> // dfa tells the number associated // with the present state int dfa = 0; // This function is for // the starting state (zeroth) of DFA void start( char c) { // On receiving 'T' or 't' goto first state (1) if (c == 't' || c == 'T' ) dfa = 1; } // This function is for the first state of DFA void state1( char c) { // On receiving 'T' or 't' goto first state (1) if (c == 't' || c == 'T' ) dfa = 1; // On receiving 'H' or 'h' goto second state (2) else if (c == 'h' || c == 'H' ) dfa = 2; // else goto starting state (0) else dfa = 0; } // This function is for the second state of DFA void state2( char c) { // On receiving 'E' or 'e' goto third state (3) // else goto starting state (0) if (c == 'e' || c == 'E' ) dfa = 3; else if (c == 't' || c == 'T' ) dfa = 1; else dfa = 0; } // This function is for the third state of DFA void state3( char c) { // On receiving 'T' or 't' goto first state (1) // else goto starting state (0) if (c == 't' || c == 'T' ) dfa = 1; else dfa = 0; } bool isAccepted( char str[]) { // store length of string int len = strlen (str); for ( int i=0; i < len; i++) { if (dfa == 0) start(str[i]); else if (dfa == 1) state1(str[i]); else if (dfa == 2) state2(str[i]); else state3(str[i]); } return (dfa != 3); } // driver code int main() { char str[] = "forTHEgeeks" ; if (isAccepted(str) == true ) printf ( "ACCEPTED" ); else printf ( "NOT ACCEPTED" ); return 0; } |
JAVA
// Java program to implement DFS that accepts // all string that do not end with "THE" import java.util.*; class GFG { // dfa tells the number associated // with the present state static int dfa = 0 ; // This function is for // the starting state (zeroth) of DFA static void start( char c) { // On receiving 'T' or 't' goto first state (1) if (c == 't' || c == 'T' ) dfa = 1 ; } // This function is for the first state of DFA static void state1( char c) { // On receiving 'T' or 't' goto first state (1) if (c == 't' || c == 'T' ) dfa = 1 ; // On receiving 'H' or 'h' goto second state (2) else if (c == 'h' || c == 'H' ) dfa = 2 ; // else goto starting state (0) else dfa = 0 ; } // This function is for the second state of DFA static void state2( char c) { // On receiving 'E' or 'e' goto third state (3) // else goto starting state (0) if (c == 'e' || c == 'E' ) dfa = 3 ; else dfa = 0 ; } // This function is for the third state of DFA static void state3( char c) { // On receiving 'T' or 't' goto first state (1) // else goto starting state (0) if (c == 't' || c == 'T' ) dfa = 1 ; else dfa = 0 ; } static boolean isAccepted( char str[]) { // store length of string int len = str.length; for ( int i= 0 ; i < len; i++) { if (dfa == 0 ) start(str[i]); else if (dfa == 1 ) state1(str[i]); else if (dfa == 2 ) state2(str[i]); else state3(str[i]); } return (dfa != 3 ); } // Driver code public static void main(String[] args) { char str[] = "forTHEgeeks" .toCharArray(); if (isAccepted(str) == true ) System.out.println( "ACCEPTED" ); else System.out.println( "NOT ACCEPTED" ); } } /* This code is contributed by PrinciRaj1992 */ |
Python3
# Python3 program to implement DFS that accepts # all stringing that do not end with "THE" # This function is for the starting # state (zeroth) of DFA def start(c): # On receiving 'T' or 't' goto # first state (1) if (c = = 't' or c = = 'T' ): dfa = 1 # This function is for the first state of DFA def state1(c): # On receiving 'T' or 't' goto first state (1) if (c = = 't' or c = = 'T' ): dfa = 1 # On receiving 'H' or 'h' goto second state (2) elif (c = = 'h' or c = = 'H' ): dfa = 2 # else goto starting state (0) else : dfa = 0 # This function is for the second state of DFA def state2(c): # On receiving 'E' or 'e' goto third # state (3) else goto starting state (0) if (c = = 'e' or c = = 'E' ): dfa = 3 else : dfa = 0 # This function is for the third state of DFA def state3(c): # On receiving 'T' or 't' goto first # state (1) else goto starting state (0) if (c = = 't' or c = = 'T' ): dfa = 1 else : dfa = 0 def isAccepted(string): # store length of stringing length = len (string) for i in range (length): if (dfa = = 0 ): start(string[i]) elif (dfa = = 1 ): state1(string[i]) elif (dfa = = 2 ): state2(string[i]) else : state3(string[i]) return (dfa ! = 3 ) # Driver Code if __name__ = = "__main__" : string = "forTHEgeeks" # dfa tells the number associated # with the present state dfa = 0 if isAccepted(string): print ( "ACCEPTED" ) else : print ( "NOT ACCEPTED" ) # This code is contributed by SHUBHAMSINGH10 |
C#
// C# program to implement DFS that accepts // all string that do not end with "THE" using System; class GFG { // dfa tells the number associated // with the present state static int dfa = 0; // This function is for // the starting state (zeroth) of DFA static void start( char c) { // On receiving 'T' or 't' goto first state (1) if (c == 't' || c == 'T' ) dfa = 1; } // This function is for the first state of DFA static void state1( char c) { // On receiving 'T' or 't' goto first state (1) if (c == 't' || c == 'T' ) dfa = 1; // On receiving 'H' or 'h' goto second state (2) else if (c == 'h' || c == 'H' ) dfa = 2; // else goto starting state (0) else dfa = 0; } // This function is for the second state of DFA static void state2( char c) { // On receiving 'E' or 'e' goto third state (3) // else goto starting state (0) if (c == 'e' || c == 'E' ) dfa = 3; else dfa = 0; } // This function is for the third state of DFA static void state3( char c) { // On receiving 'T' or 't' goto first state (1) // else goto starting state (0) if (c == 't' || c == 'T' ) dfa = 1; else dfa = 0; } static bool isAccepted( char []str) { // store length of string int len = str.Length; for ( int i=0; i < len; i++) { if (dfa == 0) start(str[i]); else if (dfa == 1) state1(str[i]); else if (dfa == 2) state2(str[i]); else state3(str[i]); } return (dfa != 3); } // Driver code static public void Main () { char []str = "forTHEgeeks" .ToCharArray(); if (isAccepted(str) == true ) Console.WriteLine( "ACCEPTED" ); else Console.WriteLine( "NOT ACCEPTED" ); } } /* This code is contributed by ajit. */ |
PHP
<?php // PHP program to implement DFS // that accepts all string that // do not end with "THE" // dfa tells the number associated // with the present state $dfa = 0; // This function is for the // starting state (zeroth) of DFA function start( $c ) { global $dfa ; // On receiving 'T' or 't' // goto first state (1) if ( $c == 't' || $c == 'T' ) $dfa = 1; } // This function is for // the first state of DFA function state1( $c ) { global $dfa ; // On receiving 'T' or 't' // goto first state (1) if ( $c == 't' || $c == 'T' ) $dfa = 1; // On receiving 'H' or 'h' // goto second state (2) else if ( $c == 'h' || $c == 'H' ) $dfa = 2; // else goto starting state (0) else $dfa = 0; } // This function is for // the second state of DFA function state2( $c ) { global $dfa ; // On receiving 'E' or 'e' // goto third state (3) else // goto starting state (0) if ( $c == 'e' || $c == 'E' ) $dfa = 3; else $dfa = 0; } // This function is for // the third state of DFA function state3( $c ) { global $dfa ; // On receiving 'T' or 't' // goto first state (1) else // goto starting state (0) if ( $c == 't' || $c == 'T' ) $dfa = 1; else $dfa = 0; } function isAccepted( $str ) { global $dfa ; // store length of string $len = strlen ( $str ); for ( $i =0; $i < $len ; $i ++) { if ( $dfa == 0) start( $str [ $i ]); else if ( $dfa == 1) state1( $str [ $i ]); else if ( $dfa == 2) state2( $str [ $i ]); else state3( $str [ $i ]); } return ( $dfa != 3); } // Driver Code $str = "forTHEgeeks" ; if (isAccepted( $str ) == true) echo "ACCEPTED" ; else echo "NOT ACCEPTED" ; // This code is contributed by m_kit ?> |
Javascript
<script> // Javascript program to // implement DFS that accepts // all string that do not end // with "THE" // dfa tells the number associated // with the present state let dfa = 0; // This function is for // the starting state (zeroth) of DFA function start(c) { // On receiving 'T' or 't' goto // first state (1) if (c == 't' || c == 'T' ) dfa = 1; } // This function is for the first state of DFA function state1(c) { // On receiving 'T' or 't' goto first state (1) if (c == 't' || c == 'T' ) dfa = 1; // On receiving 'H' or 'h' goto second state (2) else if (c == 'h' || c == 'H' ) dfa = 2; // else goto starting state (0) else dfa = 0; } // This function is for the second state of DFA function state2(c) { // On receiving 'E' or 'e' goto third state (3) // else goto starting state (0) if (c == 'e' || c == 'E' ) dfa = 3; else dfa = 0; } // This function is for the third state of DFA function state3(c) { // On receiving 'T' or 't' goto first state (1) // else goto starting state (0) if (c == 't' || c == 'T' ) dfa = 1; else dfa = 0; } function isAccepted(str) { // store length of string let len = str.length; for (let i=0; i < len; i++) { if (dfa == 0) start(str[i]); else if (dfa == 1) state1(str[i]); else if (dfa == 2) state2(str[i]); else state3(str[i]); } return (dfa != 3); } let str = "forTHEgeeks" .split( '' ); if (isAccepted(str) == true ) document.write( "ACCEPTED" ); else document.write( "NOT ACCEPTED" ); </script> |
输出：
ACCEPTED
该程序的时间复杂度为O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
