java算法：字符串

java算法：字符串

在C语言和其他语言中，串指的是长度变化的字符数组，有一个起始点和一个标识串结束的终止符。在Java中，串是具有内嵌语言支持的高级抽象结构，它的表示是隐藏的。

串是具有价值的数据结构，因为一些计算方面的应用会应用到文本数据，可以直接使用串来表示，可以直接、有效地访问内存字节，而内存字节对应着串中的字符。即，大多数情况下，串抽象结构与应用的需求相匹配，并能充分利用机器的能力。

例一：串查找

Java代码

publicstaticintcountMatches(Stringpattern,Stringsource){ intcnt=0; intM=pattern.length(); intN=source.length(); if(M>N){ return0; } for(inti=0;i<N;i++){ intj; for(j=0;j<M;j++){ if(i+j<N){ if(source.charAt(i+j)!=pattern.charAt(j)){ break; } }else{ break; } } if(j==pattern.length()){ cnt++; } } returncnt; }

public static int countMatches(String pattern, String source){int cnt = 0;int M = pattern.length();int N = source.length();if(M > N){return 0;}for (int i = 0; i < N; i++) {int j;for(j = 0; j < M; j++){if(i + j < N){if(source.charAt(i + j) != pattern.charAt(j)){break;}}else{break;}}if(j == pattern.length()){cnt++;}}return cnt;}

串的查找，它所花的时间与串的长度成正比。

如果source足够长，那么这段代码运行速度变慢，效率低下，这类问题可称为性能臭虫。因为经验验证程序代码的正确性，但是运行起来并不是我们所期望的。因此在研究有效算法之前，必须消除这类性能错误。

例二：串处理

Java代码

publicstaticStringsqueeze(Strings){ char[]a=s.toCharArray(); intN=1; for(inti=1;i<a.length;i++){ a[N]=a[i]; if(a[N]!=”){ N++; }elseif(a[N-1]!=”){ N++; } } returnnewString(a,0,N); }

public static String squeeze(String s){char [] a = s.toCharArray();int N = 1;for(int i = 1; i < a.length; i++){a[N] = a[i];if(a[N] != ' '){N++;}else if(a[N - 1] != ' '){N++;}}return new String(a, 0, N); }

返回一个串，除了把串中的连续空白符替换成单个空白符，其它与原串相同。

由于串是变化的，因此串的内存分配要比链表的内存分配难得多；但java系统再一次考虑了所有细节。事实上，一个为串预留空间的一般机制与所有的java对象所需要的一般内存分配机制是差不多的。通常当我们使用串时，串的内存分配问题并不像串第一次出现时那么重要，因为我们经常使用的是串的引用，而不是字符串本身。

而这些目标凝结成希望的萌芽，在汗水与泪水浇灌下，绽放成功之花。