給定一個模式串S，以及一個模板串P，所有字串中只包含大小寫英文字母以及阿拉伯數字，
模板串P在模式串S中多次作為子串出現，
求出模板串P在模式串S中所有出現的位置的起始下標，
輸入格式
第一行輸入整數N，表示字串P的長度，
第二行輸入字串P，
第三行輸入整數M，表示字串S的長度，
第四行輸入字串S，
輸出格式
共一行，輸出所有出現位置的起始下標（下標從0開始計數），整數之間用空格隔開，
資料范圍
1≤N≤1041≤N≤104
1≤M≤1051≤M≤105
輸入樣例：
3
aba
5
ababa
輸出樣例：
0 2
ne[i]的含義：對于子串，最長相同前綴和后綴的長度
eg:
abaacdffgab ne[i] 0 0 1 1 0 0 0 0 0 1 2
代碼：
import java.util.Scanner; public class Main{ static int m,n;//n為子串，m為父串 static int ne[]=new int[10005]; static char p[]=new char[10005]; static char s[]=new char[100005]; static void get_next(){ for(int i=2,j=0;i<=n;i++){//i從2開始，如果i=1就不匹配，那么ne[1]=0 while(j>0 &&p[i]!=p[j+1]) j=ne[j]; if(p[i]==p[j+1]) j++; ne[i]=j; } } static void kmp(){ for(int i=1,j=0;i<=m;i++){ while(j>0 && s[i]!=p[j+1]) j=ne[j]; if(s[i]==p[j+1]) j++; if(j==n){ System.out.print((i-n)+" "); j=ne[j]; } } } public static void main(String[] args) { Scanner scan=new Scanner(System.in); n=scan.nextInt(); String sn=scan.next(); m=scan.nextInt(); String sm=scan.next(); for(int i=1;i<=n;i++) p[i]=sn.charAt(i-1);//子串 for(int i=1;i<=m;i++) s[i]=sm.charAt(i-1);//父串 get_next(); kmp(); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102304.html
標籤：其他