算法题1

题目

编写一个方法，求两个字符串的最长公共子串（Longest Common Substring）的长度。
输入：
• 两个字符串 str1 和 str2。
输出：
• 它们的最长公共子串的长度（即最大连续相同子串的长度）。

测试用例

输入字符串1 输入字符串2 期望输出 说明
"abcdef" "zcdemf" 3 最长公共子串为"cde"
"12345" "34567" 3 最长公共子串为"345"
"aaaa" "aaa" 3 最长公共子串为"aaa"
"" "abc" 0 空字符串无公共子串
"abc" "" 0 空字符串

代码

public class Program
{
	static void Main(string[] args)
	{
		Console.WriteLine("Hello, World!");

		Run("abcdef", "zcdemf");
		Run("12345", "34567");
		Run("aaaa", "aaa");
		Run("", "abc");
		Run("abc", "");

		Console.ReadKey();
	}


	public static void Run(string str1, string str2)
	{

		if (string.IsNullOrEmpty(str1)  || string.IsNullOrEmpty(str2))
		{
			Console.WriteLine("无公共子串");
			return;
		}

		string targartRtr = string.Empty;
		string shorttStr = str1.Length > str2.Length ? str2 : str1;
		string longstr = shorttStr.Equals(str1) ? str2 : str1;

		for (int subIndex =shorttStr.Length;subIndex > 0;subIndex--)
		{
			for (int i = 0; (i+subIndex) <=shorttStr.Length;i++)
			{
				string substr = shorttStr.Substring(i, subIndex);
				if (longstr.IndexOf(substr) >= 0)
				{
					targartRtr = substr;
					Console.WriteLine(targartRtr);
				}
			}
			if (!string.IsNullOrEmpty(targartRtr)) //找出满足条件的跳出循环
			{
				break;
			}
		}
		
		//Console.ReadKey();
		
	}

}