BÁO CÁO BÀI TẬP NHĨM MƠN: NHẬP MƠN NGÀNH THÀNH VIÊN NHÓM: 1.TRƯƠNG LÊ QUỐC MINH 2.NGUYỄN THỊ HƯƠNG GIANG 3.NGÔ HỒ MINH HƯNG 4.PHẠM DUY TIN ĐỀ TÀI: THUẬT TỐN KNUTH-MORRIS-PRATT Nội dung 1.Tóm tắt & giới thiệu thuật tốn Giải thích thuật tốn Giới thiệu vài tốn ứng dụng I Tóm tắt & giới thiệu thuật toán (KMP)  -Thuật toán Knuth-Morris-Pratt (KMP) thuật tốn với thời gian chạy tuyến tính nhằm giải toán so khớp chuỗi  -Thuật toán xây dựng dựa vào quan sát xâu chung của S và T sẽ đưa thơng tin S có khớp với vị trí sau của T hay khơng Bởi xâu chung đồng nghĩa với phần của t đã khớp với phần s, nên việc khởi tạo trước số thông tin với xâu S, ta thu kết luận về T (nhờ xâu chung) mà không cần quay ngược so sánh lại ký tự khớp  -Cụ thể hơn, ta muốn tính tốn trước cách xâu S tự khớp với Nhờ thuật tốn sẽ khơng quay nhìn lại và duyệt qua T một lần II.Giải thích thuật tốn KMP  Ý tưởng thuật toán :  chuỗi S = aaaab chuỗi T = aab  Ý tưởng thuật toán:   Thuật toán được xây dựng dựa vào quan sát xâu chung T S sẽ đưa thơng tin T có khớp với vị trí sau của S hay khơng 2.Giải thích thuật tốn KMP Ví dụ: tìm vị trí xâu T xâu 'S' dưới, không áp dung kmp đây: Bước 1: i=1,j=1;(stt giá trị s;v)         S1=T1(a=a)  => i++;j++ Bước 2: i=2,j=2;         S2=T2(a=a) => i++;j++ i S a a a a b j T a a b i S a a a a b j T a a b Bước 3: i=3,j=3;         S3≠T3(a≠b)  => i=2;j=1 stt(i) S a a a a b stt(J) T a a b Ở ta thấy S3 khác T3, S không khớp với T vị trí Đến bước thuật tốn tiếp tục cách so T1 với S2 T2 với S3 T3 S4, không khớp; lại so T1 với S3 lúc thuật toán khớp Vậy, ta thấy so khớp chuỗi, áp dụng thuật toán bình thường mà khơng sử dụng thuật tốn kmp rơi vào trường hợp xấu tốn m*n lần so khớp=> việc làm thuật toán tốn thời gian, khơng tối ưu Ý tưởng thuật tốn KMP là:Khi ta tìm vị trí xuất xâu nhỏ xâu lớn Chúng ta xét xâu quan sát số xâu xâu lớn có khớp với xâu nhỏ hay khơng.Đây điều ta cần lưu ý thuật toán KMP để tránh so sánh vơ ích Ví dụ: tìm vị trí xâu T trong xâu 'S' dưới, áp dụng kmp : i 10 S a b c a b a b a b d j T a b a  b  d GT 0 Ở ta xét vị trí bắt đầu mẫu T Bước 1: i=1;j=0.                      S1=T(0+1)(a=a)=>i++;j++ Bước 2: i=2;j=1.                      S2=T(1+1)(b=b)=>i++;j++ Bước 3: i=3;j=2.                      S3≠T(2+1)(c≠a)=>i=i; Ta thấy T2 có giá trị => di chuyển vị trí j Bước 4: i=3;j=1.         S3≠T(0+1)(c≠a)=>i=i;Nhưng sau ta khơng thể lùi vị trí j nên ta di chuyển vị trí i sang phải(i=i+1=4) i 10 S a b c a b a b a b d j T a b a  b  d GT 0 Bước 5: i=4;j=0 S4=T(0+1)(a=a)=>i++;j++ Bước 6: i=5;j=1 S5=T(1+1)(b=b)=>i++;j++ Bước 7: i=6;j=2 S6=T(2+1)(a=a)=>i++;j++ Bước 8: i=7;j=3 S7=T(3+1)(b=b)=>i++;j++ Bước 9: i=8;j=4 S8≠T(4+1)(a≠d)=>i=i; Ta thấy T4 có giá trị => di chuyển vị trí j i 10 S a b c a b a b a b d j T a b a b d GT 0 Bước 10: i=8;j=2 S8=T(2+1)(a=a)=>i++;j++ Bước 11: i=9;j=3 S9=T(3+1)(b=b)=>i++;j++ Bước 12: i=10;j=4 S10=T(4+1)(d=d)=> kết thúc thuật toán Vậy sau 12 bước, ta xác định được chuỗi T chuỗi lớn S IV toán ứng dụng 1.Bài toán thứ nhất: A character string is said to have period k if it can be formed by concatenating one or more repetitions of another string of length k For example, the string ”abcabcabcabc” has period 3, since it is formed by repetitions of the string ”abc” It also has periods (two repetitions of ”abcabc”) and 12 (one repetition of ”abcabcabcabc”) Write a program to read a character string and determine its smallest period Input The first line of the input file will contain a single integer N indicating how many test case that your program will test followed by a blank line Each test case will contain a single character string of up to 80 non-blank characters Two consecutive input will separated by a blank line Output An integer denoting the smallest period of the input string for each input Two consecutive output are separated by a blank line Sample Input HoHoHo Sample Output #include int main() { #include int T; #define MaxL 1000 char s[MaxL]; int KMP_init(char *s) { scanf("%d", &T); int i, j; while(T ) { int next[MaxL]; scanf("%s", s); next[1] = 0, j = 0; int l = strlen(s), t = KMP_init(s); for(i = 2; s[i] != '\0'; ++i){ if(l%(l-t-1)) while(j>0 && s[j+1] != s[i]) j = next[j]; printf("%d\n", l); if(s[j+1] == s[i]) else j++; printf("%d\n", l-t-1); next[i] = j; if(T) puts(""); } } return j; return 0; } } 2.Bài toán thứ 2:In this problem you have to learn to dance the Cheeky-Cheeky This dancing consists of 4 basic     steps (as listed above) that are arranged into a particular sequence Then this sequence can be  repeated an arbitrary number of times.  For example, if the sequence is ‘123’, then the Cheeky-Cheeky is danced like this: ‘12312312312312 ’.  But if the sequence is ‘123124’, then the steps of the dancing are ‘123124123124123 ’.  You are given some of the steps of a particular dancing Those steps will contain between (inclusive) and (not inclusive) times the basic sequence. You have to continue the dancing Input  The first line of the input contains an integer indicating the number of test cases.  Sample Input 123123 1231231 Each case contains some of the first steps of a dancing It is a single line with a list of digits (1, 2,  12312312 or 4) with no spaces between them It will not have more than 2000 steps Remember that the case  123124123124 contains the basic sequence twice, and possibly has some more steps (but not thrice).  12312412312412 Output  12312412312412312 For each test case, the output should contain the following steps of the dancing, followed by three  dots ‘ ’.  Sample Output 12312312 23123123 31231231 12312412 31241231 41231241   #include getnext(n); using namespace std; int len; const int maxn = 10000; for (int i = n; i >= 1; i ) { char a[maxn]; if (pi[i] != && i % (i - pi[i]) == 0) { int pi[maxn]; len = i - pi[i]; void getnext(int n) { break; pi[1] = 0; } for (int i = 2, j = 0; i && a[i] != a[j + 1]) j = pi[j]; int s = n % len; if (a[i] == a[j + 1]) j++; int cnt = 0; pi[i] = j; for (int i = s + 1; cnt < 8; i++, cnt++) { } if (i > len) i = 1; } printf("%c", a[i]); int main() { } int _; printf(" \n"); scanf("%d", &_); } while (_ ) { return 0; scanf("%s", a + 1); int n = strlen(a + 1); } 3.Bài toán thứ 3: input: mảng ký tự, S (đoạn văn bản) mảng ký tự, W (xâu tìm) output: biến kiểu nguyên (vị trí (bắt đầu từ 0) S mà W tìm thấy) ví dụ:Tìm W khớp với S vị trí nào: S: W: ABC ABCDAB ABCDABCDABDE ABCDABD Kết quả: W khớp với S vị trí S[15] #include match         if (j > || pattern[j] == pattern[i]) { #include     int next[n + 1];             next[i + 1] = j + 1; #include           }       for (int i = 0; i < n + 1; i++) {     } // Function to implement the KMP algorithm         next[i] = 0;   void KMP(const char* text, const char* pattern, int     } m, int n)   {     for (int i = 1; i < n; i++)     // base case 1: pattern is NULL or empty     {     if (*pattern == '\0' || n == 0) {         int j = next[i + 1];         printf("The pattern occurs with shift 0");       }               for (int i = 0, j = 0; i < m; i++)     // base case 2: text is NULL, or text's length is less than that of pattern's         }     {         if (*(text + i) == *(pattern + j))         {             if (++j == n) {                 printf("The pattern occurs with shift %d\ n", i - j + 1);             }         else if (j > 0)     if (*text == '\0' || n > m) {         {         printf("Pattern not found");  while (j > && pattern[j] != pattern[i]) {     }             j = next[j];           }             i ;    // since `i` will be incremented in the next iteration     // next[i] stores the index of the next best partial           }             j = next[j]; Nguồn tài liệu tham khảo:  https://vnoi.info/wiki/translate/wcipeg/kmp.md  https://cp-algorithms.com/string/prefix-function.html ... thiệu thuật tốn Giải thích thuật tốn Giới thiệu vài tốn ứng dụng I Tóm tắt & giới thiệu thuật toán (KMP)  -Thuật toán Knuth- Morris- Pratt (KMP) thuật tốn với thời gian chạy tuyến tính nhằm giải toán. .. khớp với Nhờ thuật tốn sẽ khơng quay nhìn lại và duyệt qua T một lần II.Giải thích thuật toán KMP  Ý tưởng thuật toán :  chuỗi S = aaaab chuỗi T = aab  Ý tưởng thuật toán:    Thuật toán? ?được... Đến bước thuật toán tiếp tục cách so T1 với S2 T2 với S3 T3 S4, không khớp; lại so T1 với S3 lúc thuật toán khớp Vậy, ta thấy so khớp chuỗi, áp dụng thuật tốn bình thường mà khơng sử dụng thuật