反转字符串
写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）
import java.util.*;
public class Solution {
public String solve (String str) {
char[] cstr = str.toCharArray();
int len = str.length();
for(int i = 0 ; i < len/2 ;i++)
{
char t = cstr[i];
cstr[i] = cstr[len-1-i];
cstr[len-1-i]=t;
}
return new String(cstr);
}
}
//因为java中字符串是常量，只有用char数组实现；用其他语言实现的话这种方法无需额外空间。//法2：利用辅助空间
import java.util.*;
public class Solution {
public String solve (String str) {
char[] ans = str.toCharArray();
int len = str.length();
for(int i = 0 ; i < len ;i++)
{
ans[i] = str.charAt(len-1-i);
}
return new String(ans);
}
}//利用库函数
import java.util.*;
public class Solution {
public String solve (String str) {
StringBuffer sb =new StringBuffer(str);//此方法针对的是io流，不能针对字符串。
return sb.reverse().toString();
}
}
//或者：
if(str==null||str.length()==0) return str;
return new StringBuilder(str).reverse().toString();求子串位置
题目描述 easy 28
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
提示：字符串仅由小写英文字母构成
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
朴素算法
记原串为ss,匹配串为pp。以ss中每个字符作为，每次从原串中的和匹配串的开始尝试匹配：
- 匹配成功：返回本次匹配的原串
- 匹配失败：从下一个继续匹配
class Solution { public int strStr(String ss, String pp) { int n = ss.length(), m = pp.length(); char[] s = ss.toCharArray(), p = pp.toCharArray(); // 枚举原串的「发起点」 for (int i = 0; i <= n - m; i++) {//n=4，m=2，则主串只要到第三个就可以了 // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配 int a = i, b = 0; while (b < m && s[a] == p[b]) { a++; b++; } // 如果能够完全匹配，返回原串的「发起点」下标 if (b == m) return i; } return -1; } }
kmp算法
视频：https://www.bilibili.com/video/BV1M5411j7Xx?from=search&seid=1940287345029268873
算法基本流程是原串是不会回溯的，每次借助next数组选择匹配串合适的位置开始往后匹配。
next数组
首先明确每次用匹配串匹配原串的时候，可能会发生部分匹配的情况，这时借助next数组可以减少不必要的重复匹配。next数组根据利用已匹配部分中相同的「前缀」和「后缀」来加速下一次的匹配。
前缀：对于字符串
aabaaf，是不包含f的所有子串。后缀：是不包含第一个
a的所有子串最长相等前后缀: 对于
aabaaf是0；即f对应的next数组值为0。完整版是010120
具体实现next数组时有的是将前缀表完整右移然后令第一个为-1（在f冲突时直接找f对应的下标）；有的是整体-1（冲突时还是看前一位，只不过会加回来）；有的原封不动（冲突时看f的前一位）。原理*：
首先匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」。如果存在，则跳转到「前缀」的下一个位置继续往下匹配：
next数组构建：
对a，最长前后缀长度为0；对aa，最长前后缀长度为1；对aaa最长前后缀长度为2；对aaab，最长前后缀长度为0；
代码实现：
//本代码直接使用前缀表
//要明白一点，对于一个串aaab，前缀后缀都是有很多个的
//i:指向后缀末尾位置，同时表示当前求解的next数组位置，同时表示字符串最末位下标（指运行到的）。j指向前缀末尾位置，同时表示i之前（包括i）的子串的最长相等前后缀长度（即：j表示前缀长度-1）
//1.初始化 2. 前后缀相同 3.前后缀不同 4.next
//1.因为子串a没有前后缀，只能从aa开始初始化。故前缀结束位置j=0；后缀结束位置i=1；然后第一步前后缀相等进入3.。在aab时前后缀相同进入2.
//2.
public void getNext(char s[],int next[]){
int j=0,i=1;
next[0]=0;
for(i=1;i<s.length;i++){
while(s[i]!=s[j] && j>0){
j = next[j-1];
}
//后缀末位f!=前缀末位c，前缀长度减小(回退到上一轮的长度ab与bf同样不等，一直回退)
//这里说ab与bf不等只是便于理解，其实只用比较b与f不等即可
if(s[i]==s[j]) j++;//相等则前后缀长度都加一，再比较两个是否相同
next[i]=j;//长度变长之前要将当前字符对应的next更新到前缀的下一个位置。
//设字符串为abcabf，则当i指向b时：
//设j没有++前,最长前缀为ab(c) 最长后缀为ab(f);此时j指向第一个b，i指向第二个b
//容易发现，前后缀长度再度增加的话就会失配了（但现在并不知道
//在进行匹配时，若在f位置失配的话就需要回到c的位置开始重新匹配
//所以我们要在时f的前一个字符的next指向c。（因为我们每次调整都是用的上一个字符的next
//而c的位置就是j+1
}
}
完整代码
class Solution {
public int strStr(String haystack, String needle) {
char[] p = needle.toCharArray();
int m=needle.length();
if(m==0) return 0;//空串返回-1
int next[] = new int[m];
char[] s = haystack.toCharArray();
int n = haystack.length();
getNext(p,next);//获得next数组
for(int i=0,j=0;i<n;i++){
if(s[i]==p[j]){
j++;//若匹配则继续
}else if(j>0)
{
j=next[j-1];
i--;
//若不匹配，则i不能后移
}
if(j==m) return i-m+1;//注意此处i是匹配的最后一个字符下标；减去长度+1则是起始下标
}
return -1;
}
public void getNext(char s[],int next[]){
int j=0,i=1;
next[0]=0;
for(i=1;i<s.length;i++){
while(s[i]!=s[j] && j>0){
j = next[j-1];
}
//后缀末位f!=前缀末位c，前缀长度减小(回退到上一轮的长度ab与bf同样不等，一直回退)
//这里说ab与bf不等只是便于理解，其实只用比较b与f不等即可
if(s[i]==s[j]) j++;//相等则前后缀长度都加一，再比较两个是否相同
next[i]=j;//长度变长之前要将当前字符对应的next更新到前缀的下一个位置。
//设字符串为abcabf，则当i指向b时：
//设j没有++前,最长前缀为ab(c) 最长后缀为ab(f);此时j指向第一个b，i指向第二个b
//容易发现，前后缀长度再度增加的话就会失配了（但现在并不知道
//在进行匹配时，若在f位置失配的话就需要回到c的位置开始重新匹配
//所以我们要在时f的前一个字符的next指向c。（因为我们每次调整都是用的上一个字符的next
//而c的位置就是j+1
}
}
}释：设P为子串，当next[j]已经求得，要求next[j+1]，可以分以下两种情况分析：
- 若子串中字符Pj等于Pi，显然next[i+1]=j+1。因为j为当前P最长相等前后缀长度。
- 若Pj不等于Pi，将Pi-j+1...Pi当作主串，将P1...Pj当作子串。类似于失配问题，需移动子串，即令j=next[j]，继续进行比较，若满足1.则求得next[j+1]。
计算机用此方法计算效率很高，但不利于手工计算和理解。
算法实现
实际编码时，通常我会往原串和匹配串头部追加一个空格（哨兵）。
目的是让j下标从0开始，省去j从-1开始的麻烦。
class Solution {
// KMP 算法
// ss: 原串(string) pp: 匹配串(pattern)
public int strStr(String ss, String pp) {
if (pp.isEmpty()) return 0;
// 分别读取原串和匹配串的长度
int n = ss.length(), m = pp.length();
// 原串和匹配串前面都加空格，使其下标从 1 开始
ss = " " + ss;
pp = " " + pp;
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
// 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
int[] next = new int[m + 1];
// 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
for (int i = 2, j = 0; i <= m; i++) {
// 匹配不成功的话，j = next(j)
while (j > 0 && p[i] != p[j + 1]) j = next[j];
// 匹配成功的话，先让 j++
if (p[i] == p[j + 1]) j++;
// 更新 next[i]，结束本次循环，i++
next[i] = j;
}
// 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
for (int i = 1, j = 0; i <= n; i++) {
// 匹配不成功 j = next(j)
while (j > 0 && s[i] != p[j + 1]) j = next[j];
// 匹配成功的话，先让 j++，结束本次循环后 i++
if (s[i] == p[j + 1]) j++;
// 整一段匹配成功，直接返回下标
if (j == m) return i - m;
}
return -1;
}
}Sunday算法
一、Sunday 匹配机制
匹配机制非常容易理解：
- 目标字符串
String - 模式串
Pattern - 当前查询索引
idx（初始为 00） - 待匹配字符串
str_cut : String [ idx : idx + len(Pattern) ]
每次匹配都会从 目标字符串中 提取 待匹配字符串*与 *模式串 进行匹配：
若匹配，则返回当前 idx
不匹配，则查看 待匹配字符串 的后一位字符 c：
若c存在于Pattern中，则 idx = idx + 偏移表[c]
否则，idx = idx + len(pattern)
Repeat Loop 直到 idx + len(pattern) > len(String)
京公网安备 11010502036488号