Problem B Oulipo(KMP 기본)
7474 단어 KMP
제목 대의:
패턴열과 텍스트열을 드리겠습니다. 패턴열이 텍스트열에 나타나는 횟수를 물어보면 중첩될 수 있습니다.
코드:
1 # include<cstdio>
2 # include<iostream>
3 # include<cstring>
4
5 using namespace std;
6
7 char s2[10004];
8 char s1[1000004];
9 int nxt[10004];
10
11 void get_next()
12 {
13 int t1 = 0,t2;
14 t2 = nxt[0] = -1;
15 int len = strlen(s2);
16 while ( t1<len )
17 {
18 if ( t2==-1||s2[t2]==s2[t1] )
19 {
20 t1++;t2++;
21 nxt[t1] = t2;
22 }
23 else
24 t2 = nxt[t2];
25 }
26 }
27
28 int kmp ( char *s1, char *s2 )
29 {
30 int len1 = strlen(s1), len2 = strlen(s2);
31 int t1 = 0,t2 = 0;
32 int times = 0;
33 while ( t1 < len1 )
34 {
35 if ( t2==-1||s1[t1]==s2[t2] )
36 {
37 t1++;t2++;
38 }
39 else
40 t2 = nxt[t2];
41 if ( t2==len2 )
42 {
43 times+=1;
44 t2 = nxt[t2];
45 }
46 }
47 return times;
48 }
49
50
51 int main(void)
52 {
53 int t;scanf("%d",&t);
54 while ( t-- )
55 {
56 scanf("%s%s",s2,s1);
57 get_next();
58 int ans = kmp(s1,s2);
59 printf("%d
",ans);
60 }
61
62
63 return 0;
64 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
알고리즘 - Knuth, Morris, Prett흔히 찾는 문자나 문자열이 있는 지 없는 지를 확인할 때는 주로 if pattern in words 이런 식으로 검사를 할 수 있다. pi 테이블은 찾으려는 문자열(pattern)의 정보를 저장하고 있는 배열, 자료...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
