题目描述
给你两个字符串t和p，要求从t中找到一个和p相同的连续子串，并输出该子串第一个字符的下标。
输入描述
- 输入文件包括两行 分别表示字符串t和p
- 保证t的长度不小于p
- 且t的长度不超过1000000
- p的长度不超过10000
输出描述
- 如果能从t中找到一个和p相等的连续子串，则输出该子串第一个字符在t中的下标，下标从左到右依次为1,2,3,…；
- 如果不能，则输出 “No”
- 如果含有多个这样的子串，则输出第一个字符下标最小的
用例
| 输入 | AVERDXIVYERDIAN RDXI |
| 输出 | 4 |
| 说明 | 无 |
语言内置库函数实现
这题目的应该是想考察子串查找算法，可以考虑使用KMP算法。
但是高级语言大多已经内置实现了这些算法，比如Java的String的indexOf，JS的String.prototype.indexOf，Python的find函数
Java算法源码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(getResult(sc.nextLine(), sc.nextLine()));
}
public static String getResult(String str, String subStr) {
if (str.length() < subStr.length()) {
return "No";
}
int idx = str.indexOf(subStr);
if (idx == -1) return "No";
else return idx + 1 + "";
}
}
JS算法代码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 2) {
getSubIndex(...lines);
lines.length = 0;
}
});
/* 寻找相同子串 */
function getSubIndex(str, substr) {
if (str.length < substr.length) {
return console.log("No");
}
const index = str.indexOf(substr);
if (index === -1) {
return console.log("No");
} else {
return console.log(index + 1);
}
}
Python算法源码
# 输入获取
str = input()
subStr = input()
# 算法入口
def getResult():
if len(str) < len(subStr):
return "No"
idx = str.find(subStr)
if idx == -1:
return "No"
else:
return idx + 1
# 算法调用
print(getResult())
C算法源码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_T_LEN 1000000
#define MAX_P_LEN 10000
int main() {
char t[MAX_T_LEN];
gets(t);
char p[MAX_P_LEN];
gets(p);
char* point = strstr(t, p);
if(point == NULL) {
puts("No");
} else {
printf("%lldn", point - t + 1);
}
return 0;
}
KMP算法实现
KMP算法原理请看：
JS算法源码
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const lines = [];
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 2) {
const t = lines[0];
const p = lines[1];
const idx = indexOf(t, p);
if (idx == -1) {
console.log("No");
} else {
console.log(idx + 1);
}
lines.length = 0;
}
});
/**
* @param {*} s 正文串
* @param {*} t 模式串
* @returns 在s中查找与t相匹配的子串，如果成功找到，则返回匹配的子串第一个字符在主串中的位置
*/
function indexOf(s, t) {
let next = getNext(t);
let i = 0; // 扫描S串的指针
let j = 0; // 扫描T串的指针
// 如果 i 指针扫描到S串结束位置，或者 j 指针扫描到T串的结束位置，都应该结束查找
while (i < s.length && j < t.length) {
if (s[i] == t[j]) {
// 如果 s[i] == t[j]，则当前位置匹配成功，继续匹配下一个位置
i++;
j++;
} else {
// 如果 s[i] != t[j]，则说明当前位置匹配失败，
// 根据KMP算法，我们只需要回退T串的 j 指针到 next[j-1]位置,即最长相同前缀的结束位置后面一个位置，而S串的 i 指针保持不动
if (j > 0) {
j = next[j - 1];
} else {
// 如果 j = 0,则说明S子串subS和T在第一个字符上就匹配不上, 此时T不匹配字符T[j]前面已经没有前后缀了，因此只能匹配下一个S子串
i++;
}
}
}
// 如果最终可以在S串中找到匹配T的子串，则T串的所有字符都应该被j扫描过，即最终 j = t.length
if (j >= t.length) {
// 则S串中匹配T的子串的首字符位置应该在 i - t.length位置，因为 i 指针最终会扫描到S串中匹配T的子串的结束位置的后一个位置
return i - j;
} else {
// 否则就是没有在S中找到匹配T的子串
return -1;
}
}
function getNext(t) {
const next = new Array(t.length).fill(0);
let i = 1;
let j = 0;
while (i < t.length) {
if (t[i] == t[j]) {
next[i] = j + 1;
i++;
j++;
} else {
if (j > 0) {
j = next[j - 1];
} else {
i++;
}
}
}
return next;
}
Java算法源码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String t = sc.nextLine();
String p = sc.nextLine();
int idx = indexOf(t, p);
if (idx == -1) {
System.out.println("No");
} else {
System.out.println(idx + 1);
}
}
/**
* @param s 正文串
* @param t 模式串
* @return 在s中查找与t相匹配的子串，如果成功找到，则返回匹配的子串第一个字符在主串中的位置
*/
public static int indexOf(String s, String t) {
int[] next = getNext(t);
int i = 0; // 扫描S串的指针
int j = 0; // 扫描T串的指针
// 如果 i 指针扫描到S串结束位置，或者 j 指针扫描到T串的结束位置，都应该结束查找
while (i < s.length() && j < t.length()) {
// 如果 s[i] == t[j]，则当前位置匹配成功，继续匹配下一个位置
if (s.charAt(i) == t.charAt(j)) {
i++;
j++;
} else {
// 如果 s[i] != t[j]，则说明当前位置匹配失败，
// 根据KMP算法，我们只需要回退T串的 j 指针到 next[j-1]位置,即最长相同前缀的结束位置后面一个位置，而S串的 i 指针保持不动
if (j > 0) {
j = next[j - 1];
} else {
// 如果 j = 0,则说明S子串subS和T在第一个字符上就匹配不上, 此时T不匹配字符T[j]前面已经没有前后缀了，因此只能匹配下一个S子串
i++;
}
}
}
// 如果最终可以在S串中找到匹配T的子串，则T串的所有字符都应该被j扫描过，即最终 j = t.length
if (j == t.length()) {
// 则S串中匹配T的子串的首字符位置应该在 i - t.length位置，因为 i 指针最终会扫描到S串中匹配T的子串的结束位置的后一个位置
return i - j;
} else {
// 否则就是没有在S中找到匹配T的子串
return -1;
}
}
public static int[] getNext(String t) {
int[] next = new int[t.length()];
// 由于是将T串看出两部分，分别是后缀部分SS，和前缀部分TT
int j = 1; // j 用于扫描SS，由于含有前、后缀的串长度至少为2，因此 j 扫描后缀部分的话，至少从1开始
int k = 0; // k 用于扫描TT
// j 扫描结束
while (j < t.length()) {
if (t.charAt(j) == t.charAt(k)) {
next[j] = k + 1;
j++;
k++;
} else {
if (k > 0) {
k = next[k - 1];
} else {
j++;
}
}
}
return next;
}
}
Python算法源码
# 输入获取
t = input()
p = input()
# 生成前缀表
def getNext(t):
next = [0] * len(t)
j = 1
k = 0
while j < len(t):
if t[j] == t[k]:
next[j] = k + 1
j += 1
k += 1
else:
if k > 0:
k = next[k - 1]
else:
j += 1
return next
# KMP算法
def indexOf(s, t):
"""
:param s: 正文串
:param t: 模式串
:return: 在s中查找与t相匹配的子串，如果成功找到，则返回匹配的子串第一个字符在主串中的位置
"""
next = getNext(t)
# 手算的T串"cabaa"对应的前缀表
# next = [0, 0, 0, 0, 0]
i = 0 # 扫描S串的指针
j = 0 # 扫描T串的指针
# 如果 i 指针扫描到S串结束位置，或者 j 指针扫描到T串的结束位置，都应该结束查找
while i < len(s) and j < len(t):
# 如果 s[i] == t[j]，则当前位置匹配成功，继续匹配下一个位置
if s[i] == t[j]:
i += 1
j += 1
else:
# 如果 s[i] != t[j]，则说明当前位置匹配失败
# 根据KMP算法，我们只需要回退T串的 j 指针到 next[j-1]位置,即最长相同前缀的结束位置后面一个位置，而S串的 i 指针保持不动
if j > 0:
j = next[j - 1]
else:
# 如果 j = 0,则说明S子串subS和T在第一个字符上就匹配不上, 此时T不匹配字符T[j]前面已经没有前后缀了，因此只能匹配下一个S子串
i += 1
# 如果最终可以在S串中找到匹配T的子串，则T串的所有字符都应该被j扫描过，即最终 j = t.length
if j >= len(t):
# 则S串中匹配T的子串的首字符位置应该在 i - t.length位置，因为 i 指针最终会扫描到S串中匹配T的子串的结束位置的后一个位置
return i - j
else:
# 否则就是没有在S中找到匹配T的子串
return -1
# 算法入口
def getResult():
idx = indexOf(t, p)
if idx == -1:
print("No")
else:
print(idx + 1)
# 算法调用
getResult()
C算法源码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_T_LEN 1000000
#define MAX_P_LEN 10000
int *getNext(char *t);
int indexOf(char *s, char *t);
int main() {
char t[MAX_T_LEN];
gets(t);
char p[MAX_P_LEN];
gets(p);
int idx = indexOf(t, p);
if (idx == -1) {
puts("No");
} else {
printf("%dn", idx + 1);
}
return 0;
}
/*!
*
* @param s 正文串
* @param t 模式串
* @return 在s中查找与t相匹配的子串，如果成功找到，则返回匹配的子串第一个字符在主串中的位置
*/
int indexOf(char *s, char *t) {
int *next = getNext(t);
int sLen = strlen(s);
int tLen = strlen(t);
// 扫描S串的指针
int i = 0;
// 扫描T串的指针
int j = 0;
// 如果 i 指针扫描到S串结束位置，或者 j 指针扫描到T串的结束位置，都应该结束查找
while (i < sLen && j < tLen) {
// 如果 s[i] == t[j]，则当前位置匹配成功，继续匹配下一个位置
if (s[i] == t[j]) {
i++;
j++;
} else {
// 如果 s[i] != t[j]，则说明当前位置匹配失败，
// 根据KMP算法，我们只需要回退T串的 j 指针到 next[j-1]位置,即最长相同前缀的结束位置后面一个位置，而S串的 i 指针保持不动
if (j > 0) {
j = next[j - 1];
} else {
// 如果 j = 0,则说明S子串subS和T在第一个字符上就匹配不上, 此时T不匹配字符T[j]前面已经没有前后缀了，因此只能匹配下一个S子串
i++;
}
}
}
// 如果最终可以在S串中找到匹配T的子串，则T串的所有字符都应该被j扫描过，即最终 j = t.length
if (j == tLen) {
// 则S串中匹配T的子串的首字符位置应该在 i - t.length位置，因为 i 指针最终会扫描到S串中匹配T的子串的结束位置的后一个位置
return i - j;
} else {
// 否则就是没有在S中找到匹配T的子串
return -1;
}
}
int *getNext(char *t) {
int tLen = strlen(t);
int *next = (int *) malloc(sizeof(int) * tLen);
for (int i = 0; i < tLen; i++) {
next[i] = 0;
}
// 由于是将T串看出两部分，分别是后缀部分SS，和前缀部分TT
int j = 1; // j 用于扫描SS，由于含有前、后缀的串长度至少为2，因此 j 扫描后缀部分的话，至少从1开始
int k = 0; // k 用于扫描TT
// j 扫描结束
while (j < tLen) {
if (t[j] == t[k]) {
next[j] = k + 1;
j++;
k++;
} else {
if (k > 0) {
k = next[k - 1];
} else {
j++;
}
}
}
return next;
}免责声明：
1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文
评论0