(KMP 1.3) hdu 2087 플 라 워 스 트 립 (텍스트 문자열 에 몇 개의 패턴 문자열 이 있 는 지 확인)

2654 단어
제목:
무늬 있 는 천 조각 을 오리 다.
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; }

좋은 웹페이지 즐겨찾기