java串链式存储简单匹配(附完整源码)
时间: 2024-03-14 08:43:49 浏览: 24
串的链式存储结构是指将字符串中的每一个字符存储在一个结点中,然后使用指针将这些结点连接起来,形成一个链表。以下是Java实现串的链式存储结构的简单匹配算法的完整源码:
```java
public class StringMatch {
/**
* 串链式存储结构
*/
static class Node {
char data;
Node next;
public Node(char data) {
this.data = data;
}
}
/**
* 简单匹配算法
*
* @param s 串
* @param p 模式串
* @return 匹配成功时返回第一次匹配的位置,否则返回-1
*/
public static int match(Node s, Node p) {
Node i = s; // i指向文本串中当前比较的字符
Node j = p; // j指向模式串中当前比较的字符
Node k = null; // k指向文本串中当前需要回溯的位置
while (i != null && j != null) {
if (i.data == j.data) {
i = i.next;
j = j.next;
} else {
k = k == null ? s : k.next;
i = k;
j = p;
}
}
if (j == null) {
return k == null ? 0 : indexOf(s, k);
} else {
return -1;
}
}
/**
* 在文本串中查找子串的起始位置
*
* @param s 文本串
* @param p 子串
* @return 子串在文本串中第一次出现的位置,如果不存在则返回-1
*/
public static int indexOf(Node s, Node p) {
int i = 0;
Node j = s;
while (j != null) {
if (match(j, p) != -1) {
return i;
}
i++;
j = j.next;
}
return -1;
}
public static void main(String[] args) {
String s = "abcbcabc";
String p = "abc";
Node sNode = buildList(s);
Node pNode = buildList(p);
int pos = indexOf(sNode, pNode);
if (pos == -1) {
System.out.println("未找到匹配的子串");
} else {
System.out.println("子串\"" + p + "\"在文本串\"" + s + "\"中第一次出现的位置为:" + pos);
}
}
/**
* 将字符串转换为链表
*/
private static Node buildList(String str) {
Node head = null;
Node tail = null;
for (int i = 0; i < str.length(); i++) {
Node node = new Node(str.charAt(i));
if (head == null) {
head = node;
tail = node;
} else {
tail.next = node;
tail = node;
}
}
return head;
}
}
```
在主函数中,我们可以将文本串和模式串转换为链表,并将它们传递给indexOf方法进行匹配。如果匹配成功,indexOf方法将返回第一次匹配的位置,否则返回-1。在简单匹配算法中,我们使用i和j指针分别指向文本串和模式串中当前比较的字符,如果当前字符匹配成功,则将指针向后移动一位。如果当前字符匹配失败,则将i指针回溯到k指向的位置,并将j指针重新指向模式串的起始位置。