参考代码:
#include<bits/stdc++.h> using namespace std; const int SIZE = 2130; int perfix[SIZE]; void getPerfix(string patt) { for (int sta(0), end(1); end < patt.size();) { if (patt[sta] == patt[end]) perfix[end++] = 1 + sta++; else if (!sta) perfix[end++] = 0; else sta = perfix[sta - 1]; } } void KMP(string text, string patt) { getPerfix(patt); int Indst(0), Indnd(0); while (Indst < text.size() && Indnd < patt.size()) { if (text[Indst] == patt[Indnd]) Indst++, Indnd++; else if (!Indnd) Indst++; else Indnd = perfix[Indnd - 1]; } cout << (Indnd == patt.size() ? Indst - patt.size() + 1 : 0) << endl; return; } int main() { ios::sync_with_stdio(false); string text, patt; while (cin >> text >> patt) { KMP(text, patt); text.clear(); patt.clear(); } }
0.0分
0 人评分
C二级辅导-进制转换 (C语言代码)浏览:811 |
点我有惊喜!你懂得!浏览:1336 |
C二级辅导-等差数列 (C语言代码)浏览:569 |
C语言程序设计教程(第三版)课后习题12.5 (C语言代码)浏览:821 |
数列 (C++代码)浏览:664 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:677 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:583 |
ASCII帮了大忙浏览:748 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:459 |
C语言程序设计教程(第三版)课后习题8.2 (C语言代码)浏览:5228 |