輸入兩個字符串s1和s2，輸出s2在s1中出現的位置(位置從0開始) input
abcdefghidefdddeeeffdefeddefoutput
3920實質上是MP算法
#include<cstdio> #include<algorithm> #include<cstring> #define ms(i,j) memset(i,j, sizeof i); using namespace std;char s1[1000000 + 5], s2[1000 + 5]; int next[1000 + 5];int n,m; void getNext()//獲得失配函數 { next[0] = 0; next[1] = 0; for (int i=1;i<m;i++) { int j = next[i]; while (j && s2[i]!=s2[j]) j = next[j]; next[i+1] = ((s2[i]==s2[j]) ? (j+1) : (0)); }}void kmp()//在s1里找s2 { getNext(); int j = 0; for (int i=0;i<n;i++) { while (j && s1[i]!=s2[j]) j = next[j]; if (s1[i]==s2[j]) j++; if (j==m) KMP求字符串中的最短周期(循環節)： poj 2406 Power Strings#include<cstdio> #include<algorithm> #include<cstring> #define ms(i,j) memset(i,j, sizeof i); using namespace std;const int MAXN = 1000000 + 5;int n;char s[MAXN];int f[MAXN];int main() { while (scanf("%s", s)&&(s[0]!='.')) { n = strlen(s); f[0] = f[1] = 0; for (int i=1;i<n;i++) { int j = f[i]; while (j && s[i]!=s[j]) j = f[j]; f[i+1] = (s[i]==s[j]) ? (j+1) : (0); } int ans = n-f[n]; if (n%ans==0) ans = n/ans; else ans = 1; printf("%d/n", ans); } return 0; }新聞熱點
疑難解答
