(KMP 1.3) hdu 2087 플 라 워 스 트 립 (텍스트 문자열 에 몇 개의 패턴 문자열 이 있 는 지 확인)
무늬 있 는 천 조각 을 오리 다.
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 10380 Accepted Submission(s): 6684
Problem Description
꽃무늬 천 조각, 안에 도안 이 있 고 직접 사용 할 수 있 는 작은 장식 이 있 으 며 안에 도 도안 이 있다.주어진 꽃무늬 와 작은 장식 줄 에 대해 서 는 꽃무늬 에서 가능 한 한 몇 개의 작은 장식 줄 을 자 를 수 있 는 지 계산 해 보 세 요.
Input
입력 에 일부 데 이 터 를 포함 하고 있 습 니 다. 각각 꽃무늬 와 작은 장식 줄 입 니 다. 그 천 은 모두 가시 적 인 ASCII 문자 로 표 시 됩 니 다. 보 이 는 ASCII 문자 가 몇 개 이 고 천의 무늬 도 몇 가지 무늬 가 있 습 니까?꽃무늬 와 작은 장식 은 1000 자 를 넘 지 않 는 다.\# 문 자 를 만나면 작업 을 하지 않 습 니 다.
Output
출력 은 무늬 천 에서 가장 많이 자 를 수 있 는 작은 장식 개수 입 니 다. 한 조각 도 없 으 면 0 을 성실 하 게 출력 하고 결과 마다 줄 을 바 꿔 야 합 니 다.
Sample Input
abcde a3
aaaaaa aa
#
Sample Output
0
3
Author
qianneng
Source
겨울 에 삼 구 의 이 를 훈련 하 다.
Recommend
lcy | We have carefully selected several similar problems for you: 3746 3336 1358 2091 3068
제목 분석:
KMP.주의해 야 할 것 은 텍스트 문자열 text 가 "aaaa"이 고 패턴 문자열 이 "aa"라면 이 때 출력 결 과 는 5 가 아 닌 3 이 어야 합 니 다.
코드 는 다음 과 같 습 니 다:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1001;
int n;//
int m;//
char text[maxn];//
char pattern[maxn];//
int nnext[maxn];//next . next
/*O(m) next */
void get_next() {
nnext[0] = nnext[1] = 0;
for (int i = 1; i < m; i++) {
int j = nnext[i];
while (j && pattern[i] != pattern[j])
j = nnext[j];
nnext[i + 1] = pattern[i] == pattern[j] ? j + 1 : 0;
}
}
/*o(n)
*
*
*/
int kmp() {
int ans = 0;//
// .
int j = 0;
for (int i = 0; i < n; i++) {/* */
while (j && pattern[j] != text[i])/* ， ， j = 0*/
j = nnext[j];
if (pattern[j] == text[i])/* */
j++;
if (j == m) {/* */
ans++;
/**
* aaaaaa aa 3 5
*/
j=0;
}
}
return ans;
}
int main() {
while (scanf("%s",text)!=EOF) {
if(text[0] == '#'){
break;
}
scanf("%s",pattern);
n = strlen(text);
m = strlen(pattern);
get_next();
printf("%d
", kmp());
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
