題目描述

給出兩個字符串?s1??和?s2?，若?s1??的區(qū)間?[l,r]?子串與?s2??完全相同，則稱?s2??在?s1??中出現(xiàn)了，其出現(xiàn)位置為?l。
現(xiàn)在請你求出?s2??在?s1??中所有出現(xiàn)的位置。

定義一個字符串?s?的 border 為?s?的一個非?s?本身的子串?t，滿足?t?既是?s?的前綴，又是?s?的后綴。
對于?s2?，你還需要求出對于其每個前綴?s′?的最長 border?t′?的長度。

輸入格式

第一行為一個字符串，即為?s1?。
第二行為一個字符串，即為?s2?。

輸出格式

首先輸出若干行，每行一個整數(shù)，按從小到大的順序輸出?s2??在?s1??中出現(xiàn)的位置。
最后一行輸出?∣s2?∣?個整數(shù)，第?i?個整數(shù)表示?s2??的長度為?i?的前綴的最長 border 長度。

輸入輸出樣例

輸入 #1復制運行

ABABABC
ABA

輸出 #1復制運行

1
3
0 0 1 

說明/提示

樣例 1 解釋

。

對于?s2??長度為?3?的前綴?ABA，字符串?A?既是其后綴也是其前綴，且是最長的，因此最長 border 長度為?1。

數(shù)據(jù)規(guī)模與約定

本題采用多測試點捆綁測試，共有 3 個子任務。

• Subtask 1（30 points）：∣s1?∣≤15，∣s2?∣≤5。
• Subtask 2（40 points）：∣s1?∣≤104，∣s2?∣≤102。
• Subtask 3（30 points）：無特殊約定。

對于全部的測試點，保證?1≤∣s1?∣,∣s2?∣≤106，s1?,s2??中均只含大寫英文字母。

解題思路：

這里用的是kmp算法。也就是先確定s2的next數(shù)組，再在s1里面看有無s2字符串【kmp算法的優(yōu)點在于它是一個線性查找O(m+n)】

先確定next數(shù)組：

vector<long long> build_next(string b){vector<long long> nexts;nexts.push_back(0);long long i=0,j=1;for(;j<b.size();){if(b[j]==b[i]){i++;j++;nexts.push_back(i);}else{if(i==0){j++;nexts.push_back(i);}else{i=nexts[i-1];}}}return nexts;
}

?再跟據(jù)next數(shù)組線性查找s2字符串：

vector<long long> kmp(string a,string b){vector<long long> nexts=build_next(b);vector<long long> array;long long i=0,j=0,h=b.size();for(;j<a.size();){if(a[j]==b[i]){i++;j++;}else{if(i==0){j++;}else{i=nexts[i-1];}}if(i==h){array.push_back(j-i+1);i=nexts[i-1];}}return array;
}

總體代碼：

#include<bits/stdc++.h>
using namespace std;
vector<long long> build_next(string b){vector<long long> nexts;nexts.push_back(0);long long i=0,j=1;for(;j<b.size();){if(b[j]==b[i]){i++;j++;nexts.push_back(i);}else{if(i==0){j++;nexts.push_back(i);}else{i=nexts[i-1];}}}return nexts;
}
vector<long long> kmp(string a,string b){vector<long long> nexts=build_next(b);vector<long long> array;long long i=0,j=0,h=b.size();for(;j<a.size();){if(a[j]==b[i]){i++;j++;}else{if(i==0){j++;}else{i=nexts[i-1];}}if(i==h){array.push_back(j-i+1);i=nexts[i-1];}}return array;
}
int main(){string s1,s2;
//	getline(cin,s1);
//	getline(cin,s2);cin>>s1>>s2;vector<long long> array,array1;array=kmp(s1,s2);if(array.size()){for(long long i=0;i<array.size();i++){cout<<array[i]<<endl;}}array1=build_next(s2);for(long long i=0;i<array1.size();i++){cout<<array1[i]<<" ";}return 0;
}

?【！！！！這里string字符串輸入只能用cin，不要用getline，具體我也不知道為什么有知道歡迎在評論區(qū)中解答！！！！]