程序员编程艺术原文出自大神:v_JULY_v 地址:http://blog.csdn.net/v_july_v/article/category/784066
c++实现.敬请膜拜。
字符串问题虽基础，变化却是令人发指=—=，随便改改就能让人纠结半天。。继续砸瓷实基础，基础，基础。
原文C++实现，现将自己实现的java版本记录如下，不定期更新，自我监督，自我监督。
跳过了第三章的排序内容，因为需要去了解一些细节
继续提升编程能力和习惯，先把之后的实现。
第一节、字符串查找
1.1题目描述：
给定一个字符串A，要求在A中查找一个子串B。
如A="ABCDF"，要你在A中查找子串B=“CD”。
常用的两种方式，暴力破解法和KMP算法。
KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字（接下来称它为P），如果它在一个主串（接下来称为T）中出现，就返回它的具体位置，否则返回-1（常用手段）。
首先，对于这个问题有一个很单纯的想法：从左到右一个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动一位。这有什么难的？
我们可以这样初始化：
之后我们只需要比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动，如果不一致，如下图：
A和E不相等，那就把i指针移回第1位（假设下标从0开始），j移动到模式串的第0位，然后又重新开始这个步骤：
暴力破解法，时间复杂度O（n*m）【我们知道实际应用中这种方式消耗就很高了】
(注:在代码风格异常判断的时候，多看几种代码，养成采众家之长的习惯。干净漂亮规整的代码，对后期发展的好处不是一点噢)
主体代码如下：
public class StrStr {
public static void main(String args[]){
String str1="ABCDEFGHIJKLMN";
String str2="GHI";
String str3="WEREIJG";
System.out.println(getInNum(str1,str2));
}
public static int getInNum(String str1,String str2){
int num=0;
if(str1==null||str2==null){
return -1;
}
char[] a=str1.toCharArray();
char[] b=str2.toCharArray();
if(a.length<b.length){
return -1;
}
int i=0;//主串位置
int j=0;//子串位置
while(i<a.length&&j<b.length){
if(a[i]==b[j]){// 当两个字符相同，就比较下一个
i++;
j++;
}else{
i=i-j+1;// 一旦不匹配，i后退
j=0;// j归0
}
}
//开始对于循环外判断有疑问，debug发现j已经不小于b.length了 循环被跳出
if(j==b.length){
return i-j;
}
else{
return -1;
}
}
//个人倾向第一种方式 这个是原作者方式，个人感觉逻辑不够清晰 返回的i+1也值得商榷
public static int getInNum2(String str1,String str2){
int num=0;
if(str1==null||str2==null){
return -1;
}
char[] a=str1.toCharArray();
char[] b=str2.toCharArray();
if(a.length<b.length){
return -1;
}
int i,j;
for(i=0;i<a.length;i++){
for(j=0;j<b.length;j++){
if(a[i+j]!=b[j]){
break;
}
}
if(j==b.length){
return i+1;
}
}
return -1;
}
}
KMP方法
KMP算法看了很多，每一个都挺详细但是清晰的不多，下边列举几种说明，也许单独看某个说明不好理解，结合起来看，就可以明白位移量的关键原理了。
http://billhoo.blog.51cto.com/2337751/411486
(下述字符若带下标，则对应于图中画圈字符)
这里模式串 P = “ababaca”,在匹配了 q=5 个字符后失配，因此，下一步就是要考虑将P向右移多少位进行新的一轮匹配检测。传统模式中，直接将P右移1位，也就是将P的首字符'a'去和目标串的'b'字符进行检测，这明显是多余的。通过我们肉眼的观察，可以很简单的知道应该将模式串P右移到下图'a3'处再开始新一轮的检测，直接跳过肯定不匹配的字符'b'，那么我们“肉眼”观察的这一结果怎么把它用语言表示出来呢？
我们的观察过程是这样的： P的前缀"ab"中'a' != 'b'，又因该前缀已经匹配了T中对应的"ab"，因此，该前缀的字符'a1'肯定不会和T中对应的字串"ab"中的'b'匹配，也就是将P向右滑动一个位移是无意义的。 接下来考察P的前缀"aba"，发现该前缀自身的前缀'a1'与自身后缀'a2'相等，"a1 b a2" 已经匹配了T中的"a b a3"，因此有 'a2' == 'a3', 故得到 'a1' == 'a3'...... 利用此思想，可推知在已经匹配 q=5 个字符的情况下，将P向右移 当且仅当 2个位移时，才能满足既没有冗余(如把'a'去和'b'比较)，又不会丢失(如把'a1' 直接与 'a4' 开始比较，则丢失了与'a3'的比较)。 而前缀函数就是这样一种函数，它决定了q与位移的一一对应关系，通过它就可以间接地求得位移s。 通过对各种模式串进行上述分析(大家可以自己多写几个模式串出来自己分析理解)，发现给定一个匹配字符数 q ，则唯一对应一个有效位移，如上述q=5,则对应位移为2. 这就形成了一一对应关系，而这种唯一的关系就是由前缀函数决定的。 这到底是怎样的一种关系呢？ 通过对诸多模式串实例的研究，我们会找到一个规律（规律的证明及引理详见《算法导论(第二版)》）。 上例中，P 已经匹配的字符串为"ababa",那么这个字符串中，满足既是自身真后缀(即不等于自身的后缀)，又是自身最长前缀的字符串为"aba"，我们设这个特殊字串的长度为L，显然，L = 3. 故我们要求的 s = q - L = 5 - 3 = 2 ，满足前述分析。 根据这个规律，即可得到我们要求的有效位移s，等于已经匹配的字符数 q 减去长度 L。 即 s = q - L 因为这个长度 L 与 q 一一对应，决定于q，因此用一函数来表达这一关系非常恰当，这就是所谓的前缀函数了。 因为已经分析得到该关系为一一对应关系，因此用数组来表示该函数是比较恰当的，以数组的下标表示已经匹配的字符数 q，以下标对应的数据存储 L。
了解了前缀函数原理，也就是说我们可以计算出位移量，那么后续移位的形式就和单步一样了。
所以KMP算法的关键在于，确定next的位置.
next的确定就是找到已经匹配的字符串既是自身真后缀，又是自身最长前缀的字符串长度 用总长度减之，就是我们指针要挪的next位了。
所以问题转化为，找一个字符串中，相等的最长前缀与自身真后缀。和用next位再次对比的事情。
实现代码如下:
public class KMP {
public static void main(String args[]){
String str1= "abcdeababcdqqabcdeabc";
String str2= "abcdeabc";
String str3="abcd";
System. out.println(strIn(str1,str2));
System. out.println(kmp(str1,str2));
}
public static int strIn(String str1,String str2){
char[] a=str1.toCharArray();
char[] b=str2.toCharArray();
int i=0;
int j=0;
while(i<a.length &&j<b.length){
if(a[i]==b[j]){
i++;
j++;
} else{
i=i-j+1;
j=0;
}
} if(j==b.length ){
return i-j;
}
return -1;
}
public static int kmp(String str1,String str2){
char[] a=str1.toCharArray();
char[] b=str2.toCharArray();
int[] next=getNext(b);
int j=0;
for(int i=0;i<a.length;i++){
//当找到第一个匹配字符时，即j>0，且后续不匹配，才会执行这个循环，去找合适的回退位置
while(j>0&&b[j]!=a[i]){
//j退回合适的回退位置
j=next[j-1];
}
//如果匹配，j++
if(b[j]==a[i]){
j++;
}
if(j==b.length ){
//return i-j;
System. out.println(i-j);
//j=next[j-1];
return i-j;
}
}
return -1;
}
public static int[] getNext(char[] b){
int next[]=new int[b.length];
next[0]=0;
int j=0;
//为何i=1?对比
for(int i=1;i<b.length;i++){
//第一个匹配之后
while(j>0&&b[j]!=b[i]){
j=next[j];
}
if(b[j]==b[i]){
j++;
}
next[i]=j;
}
return next;
}
}
public class KMP {
/**
* 对子串加以预处理，从而找到匹配失败时子串回退的位置 找到匹配失败时的最合适的回退位置，而不是回退到子串的第一个字符，即可提高查找的效率
* 因此为了找到这个合适的位置，先对子串预处理，从而得到一个回退位置的数组
* @param B，待查找子串的char数组
* @return
*/
public static int[] preProcess(char[] b) {
int size = b.length;
int[] P = new int[size];
P[0] = 0;
int j = 0;
// 每循环一次，就会找到一个回退位置
for (int i = 1; i < size; i++) {
// 当找到第一个匹配的字符时，即j>0时才会执行这个循环
// 或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
// p1
while (j > 0 && b[j] != b[i]) {
j = P[j];
}
// p2，由此可以看出，只有当子串中含有重复字符时，回退的位置才会被优化
if (b[j] == b[i]) {
j++;
}
// 找到一个回退位置j，把其放入P[i]中
P[i] = j;
}
return P;
}
/**
* KMP实现
*
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] b = subStr.toCharArray();
char[] a = parStr.toCharArray();
int[] P = preProcess(b);
int j = 0;
int k = 0;
for (int i = 0; i < parSize; i++) {
// 当找到第一个匹配的字符时，即j>0时才会执行这个循环
// 或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
// p1
while (j > 0 && b[j] != a[i]) {
// 找到合适的回退位置
j = P[j - 1];
}
// p2 找到一个匹配的字符
if (b[j] == a[i]) {
j++;
}
// 输出匹配结果，并且让比较继续下去
if (j == subSize) {
j = P[j - 1];
k++;
System.out.printf("Find subString '%s' at %d\n", subStr, i
- subSize + 1);
}
}
System.out.printf("Totally found %d times for '%s'.\n\n", k, subStr);
}
public static void main(String[] args) {
// 回退位置数组为P[0, 0, 0, 0, 0, 0]
// kmp("abcdeg, abcdeh, abcdef!这个会匹配1次", "abcdef");
// 回退位置数组为P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!这个会匹配2次", "ititit");
// 回退位置数组为P[0, 0, 0]
kmp("测试汉字的匹配，张三。这个会匹配1次", "张三");
// 回退位置数组为P[0, 0, 0, 1, 2, 3, 4, 5, 6]
kmp("这个会匹配0次", "it1it1it1");
}
}
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
/**
* KMP算法的实现
* @author dfeng
*
*/
public class KMPAlgorithm {
/**
* 判断是否匹配
* @param target 目标文本串
* @param mode 模式串
* @return 匹配结果
*/
public static int matchString(String target, String mode) {
//为了和算法保持一致，使index从1开始，增加一前缀
String newTarget = "x" + target;
String newMode = 'x' + mode;
int[] K = calculateK(mode);
int i = 1;
int j = 1;
while(i <= target.length() && j <= mode.length()) {
if (j == 0 || newTarget.charAt(i) == newMode.charAt(j)) {
i++;
j++;
} else {
j = K[j];
}
}
if (j > mode.length()) {
return j;
}
return -1;
}
/*
* 计算K值
*/
private static int[] calculateK(String mode) {
//为了和算法保持一致，使index从1开始，增加一前缀
String newMode = "x" + mode;
int[] K = new int[newMode.length()];
int i = 1;
K[1] = 0;
int j = 0;
while(i < mode.length()) {
if (j == 0 || newMode.charAt(i) == newMode.charAt(j)){
i++;
j++;
K[i] = j;
} else {
j = K[j];
}
}
return K;
}
/**
* @param args
*/
public static void main(String[] args) {
String a = "bcabcabcabbcabcabcabcab";
String b = "bcabcabcabc";//"ababbaaba";//
System.out.println(KMPAlgorithm.matchString(a, b));
}
}
---------------------------------------------------------------------------------------------------------------------------------------------
参考资料:
http://www.cnblogs.com/yjiyjige/p/3263858.html
http://billhoo.blog.51cto.com/2337751/411486
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
1.2、题目描述
在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。
代码则可以如下编写：
public class test01 {
//此方法用到了indexOf(char,startIndex)
public static void main(String[] args){
String string="abcdace";
for(int i=0;i<string.length();i++){
char c = string.charAt(i);
if(string.indexOf(c, i+1) == -1){
System.out.println(c);
break;
}
}
}
}
---------------------------------------------------------------------------------------public class test01 { //此处用到indexOf和lastIndexOf public static void main(String[] args){ String string="abcdace"; for(int i=0;i<string.length();i++){ char c = string.charAt(i);System.out.println(string.indexOf(c));System.out.println(string.lastIndexOf(c)); if(string.indexOf(c) == string.lastIndexOf(c)){ System.out.println(c); break; } } }}
找出现多次的字符-------------------------------------------------------------------------------------public class test01 { public static void main(String[] args){ String string="abcdace"; for(int i=0;i<string.length();i++){ char c = string.charAt(i); if(string.indexOf(c, i+1) != -1){ System.out.println(c); break; } } }}
-------------------------------------------------------------------------------------public class test01 { //此处用到indexOf和lastIndexOf public static void main(String[] args){ String string="abcdace"; for(int i=0;i<string.length();i++){ char c = string.charAt(i); if(string.indexOf(c) != string.lastIndexOf(c)){ System.out.println(c); break; } } }}
------------------------------------------------------------------------------------需改进的hashmap方法import java.util.HashMap;import java.util.Scanner;public class StringFirst {public static void main(String args[]){ Scanner scanner=new Scanner(System. in); System. out.print("请输入字符串:" ); String str=scanner.nextLine(); System. out.print(str); char []strArray=str.toCharArray(); HashMap<Character,Integer> map= new HashMap<Character,Integer>(); for(int i=0;i<strArray.length;i++){ if(map.containsKey(strArray[i])) { map.put(strArray[i],map.get(strArray[i])+1); } else{ map.put(strArray[i], 1); }} System. out.println(map); for(int i=0;i<strArray.length;i++){ if(map.get(strArray[i])==1){ System. out.print("第一个出现一次的字符是" +strArray[i]); break; } } }}
第二节、字符串拷贝
题目描述：
要求实现库函数strcpy，
原型声明：extern char *strcpy(char *dest,char *src);
功能：把src所指由NULL结束的字符串复制到dest所指的数组中。
说明：src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串。
返回指向dest的指针。
这个有点迷糊，不太理解此题意义。。因为实在是简单，是否题目理解错误。
public class StrCopy {
public static void main(String args[]){
String str="ashdkiwekfsgmnklrger";
String str1=strCopy(str);
System.out.println(str1);
}
public static String strCopy(String str){
char[] a=str.toCharArray();
char[] b=new char[a.length];
for(int i=0;i<a.length;i++){
b[i]=a[i];
}
return new String(b);
}
}