Merge pull request #1 from symkmk/symkmk-patch-1

symkmk · web-flow · commit 98017fcb56a9 · 2018-11-25T03:48:04.000-06:00
Create 妮可.md
diff --git a/2019.11.24/妮可.md b/2019.11.24/妮可.md
@@ -0,0 +1,110 @@
+```java
+package sy181124;
+
+/*
+ * 判断一个字符串在另一个字符串中出现的位置。如果不匹配就返回-1。
+ */
+public class leetcode28实现indexof_KMP
+{
+
+	public static void main(String[] args)
+	{
+		System.out.println(index("asdf12", "12"));
+		System.out.println(KMP("bnghd12sd34", "ghd1"));
+
+	}
+	
+	/**
+	 * 暴力解法
+	 * @param a
+	 * @param b
+	 * @return
+	 */
+	public static int index(String a,String b)
+	{
+		if(a==null || b==null || a.length()<b.length())
+			return -1;
+		if(b.length()==0)
+			return 0;
+		for(int i=0;i<a.length();i++)
+		{
+			if(i+b.length()>a.length())
+				return -1;
+			
+			int index=i;
+			int j=0;
+			for( j=0;j<b.length();j++)
+			{
+				if(b.charAt(j)==a.charAt(index))
+					index++;
+				else
+					break;
+			}
+			if(j==b.length())
+				return i;
+			
+		}
+		return -1;
+		
+	}
+	
+	/**
+	 * KMP
+	 * @param a
+	 * @param b
+	 * @return
+	 */
+	public static int KMP(String a,String b)
+	{
+		if(a==null || b==null || a.length()<b.length())
+			return -1;
+		if(b.length()==0)
+			return 0;
+		char[] str1=a.toCharArray();
+		char[] str2=b.toCharArray();
+		int i1=0;
+		int i2=0;
+		int[] next=getNext(str2);
+		
+		while(i1<str1.length && i2<str2.length)
+		{
+			if(str1[i1]==str2[i2])
+			{
+				i1++;
+				i2++;
+				
+			}
+			else if (next[i2]==-1) {
+				i1++;
+			}
+			else {
+				i2=next[i2];
+			}
+		}
+		return i2==str2.length?i1-i2:-1;
+	}
+
+	private static int[] getNext(char[] str2)
+	{
+		if(str2.length==1)
+			return new int[]{-1};
+		int [] next=new int [str2.length];
+		next[0]=-1;
+		next[1]=0;
+		int i=2;
+		int cn=0;
+		while(i<next.length)
+		{
+			if(str2[i-1]==str2[cn])
+				next[i++]=++cn;
+			else if (cn>0) {
+				cn=next[cn];
+			}
+			else
+				next[i++]=0;
+		}
+		return next;
+	}
+
+}
+```
