采用顺序结构存储串,编写一个算法,求串[tex=0.5x0.786]ICKY+F5VdoSQrRn/wUUOyw==[/tex]和串[tex=0.429x0.929]r8lLiDb0KHTzu/2y/Au89w==[/tex]的一个最长公共子串。
举一反三
- 设[tex=0.786x1.0]as0RCzgUx1oS48cKHRAVVg==[/tex]是定义在所有位串集合上的关系，[tex=1.643x1.0]Kqo7xjU3OBYrrdLAfqfD/w==[/tex]当且仅当[tex=0.5x0.786]ICKY+F5VdoSQrRn/wUUOyw==[/tex]和[tex=0.429x0.929]r8lLiDb0KHTzu/2y/Au89w==[/tex]包含相同个数的1,证明[tex=0.786x1.0]as0RCzgUx1oS48cKHRAVVg==[/tex]是等价关系。
- 设[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]是正整数， [tex=0.643x1.0]fYkALuFzYlFm0R716i1EGA==[/tex]是字符串集合。假定[tex=1.214x1.214]ioLW3bPL4oDgkfrszr+FjA==[/tex]是[tex=0.643x1.0]fYkALuFzYlFm0R716i1EGA==[/tex]上的关系，[tex=2.071x1.214]ad3WAF+lcBd70r3QlTmQfA==[/tex]当且仅当[tex=1.643x0.929]72cTTnfdAQdKUTXaPt2dig==[/tex]或者[tex=0.5x0.786]ICKY+F5VdoSQrRn/wUUOyw==[/tex]和[tex=0.429x0.929]r8lLiDb0KHTzu/2y/Au89w==[/tex]都至少含有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个字符，且[tex=0.5x0.786]ICKY+F5VdoSQrRn/wUUOyw==[/tex]和[tex=0.429x0.929]r8lLiDb0KHTzu/2y/Au89w==[/tex]的前[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个字符相同。就是说，少于[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个字符的字符串只与它自身以关系[tex=1.214x1.214]ioLW3bPL4oDgkfrszr+FjA==[/tex]相关；一个至少含有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个字符的字符串[tex=0.5x0.786]ICKY+F5VdoSQrRn/wUUOyw==[/tex]与字符串[tex=0.429x0.929]r8lLiDb0KHTzu/2y/Au89w==[/tex]相关当且仅当[tex=0.429x0.929]r8lLiDb0KHTzu/2y/Au89w==[/tex]也含有至少[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个字符且[tex=0.429x0.929]r8lLiDb0KHTzu/2y/Au89w==[/tex]以[tex=0.5x0.786]ICKY+F5VdoSQrRn/wUUOyw==[/tex]最前面的[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个字符开始。例如，设[tex=2.5x1.0]uffY1+fF2svnUrhtBOi6iQ==[/tex]，[tex=0.643x1.0]fYkALuFzYlFm0R716i1EGA==[/tex]是所有位串的集合，[tex=2.0x1.214]102dWa+xgInX/PhKybX8HQ==[/tex]当[tex=1.643x0.929]72cTTnfdAQdKUTXaPt2dig==[/tex]或者[tex=0.5x0.786]ICKY+F5VdoSQrRn/wUUOyw==[/tex]和[tex=0.429x0.929]r8lLiDb0KHTzu/2y/Au89w==[/tex]均为长度至少为3的位串，且前3位相同。例如，[tex=3.786x1.214]byiyzqj0xKpOsBEbNsiOVg==[/tex]、[tex=6.786x1.214]0NVlrXG0lLNO82+Z/kE0NcyeKmdJbSHSHvBoWiZdPCs=[/tex],但[tex=4.714x1.214]77Ja2EOYwrjkn9zYN210IU1L9d67Sl8oSFT/pL73AzQ=[/tex]、[tex=7.214x1.214]/H0k3W5vbnhqjtXRWh/IhNB4RJPCSAynzzTk+FclOzw=[/tex]。证明：对所有的字符串集[tex=0.643x1.0]fYkALuFzYlFm0R716i1EGA==[/tex]和所有的正整数[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]，[tex=1.214x1.214]ioLW3bPL4oDgkfrszr+FjA==[/tex]是定义在[tex=0.643x1.0]fYkALuFzYlFm0R716i1EGA==[/tex]上的等价关系。[br][/br]
- 采用顺序结构存储串,编写一个算法计算指定子串在一个字符串中出现的次数,如果该子串不出现则为[tex=0.5x1.0]Sc0he7miKB3YF9rgXf2dDw==[/tex]。
- 设计一个算法[tex=6.071x1.357]ZYUTFo/NzHeh/69bXBYFWQ==[/tex],将一个广义表[tex=0.5x1.0]wLRBXo571ziKptAIyBBTRQ==[/tex]中的所有原子[tex=0.5x0.786]ICKY+F5VdoSQrRn/wUUOyw==[/tex]替换成[tex=0.429x0.929]r8lLiDb0KHTzu/2y/Au89w==[/tex]。例如,[tex=15.357x1.429]fS91HT+GaMuGBu0I2J5lgUVHZ9ORAk5eDtTt3VXth19becMFTrR0TWBrC1HrvXPNef+y4LmBG5tbTAyEBrL0OQ==[/tex]返回的结果为[tex=8.357x1.357]39N+AaILFXhbB9eJS4fieCKYQcqX79QMCv8de4PvM1U=[/tex]。
- 假设定长顺序存储结构表示串试设计一个算法求串s和串t的一个最长公共子串，并分析你的算法的时间复杂度若要求第一个出现的最长公共子串（既它在串s和串t的最左边的位置上出现）和所有的最长公共子串，讨论你的算法能否实现。