Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define Max 1000005
- #define PatM 1005
- queue<int> result;
- char txt[Max], pat[PatM];
- void computeLPSArray(int M, int *lps) {
- int len = 0; // lenght of the previous longest prefix suffix
- int i;
- lps[0] = 0; // lps[0] is always 0
- i = 1;
- // the loop calculates lps[i] for i = 1 to M-1
- while(i < M) {
- if(pat[i] == pat[len]) {
- len++;
- lps[i] = len;
- i++;
- } else { // (pat[i] != pat[len])
- if( len != 0 ) {
- // This is tricky. Consider the example AAACAAAA and i = 7.
- len = lps[len-1];
- // Also, note that we do not increment i here
- } else { // if (len == 0)
- lps[i] = 0;
- i++;
- }
- }
- }
- }
- void KMPSearch() {
- int M = strlen(pat);
- int N = strlen(txt);
- // create lps[] that will hold the longest prefix suffix values for pattern
- int *lps = (int *)malloc(sizeof(int)*M);
- int j = 0; // index for pat[]
- // Preprocess the pattern (calculate lps[] array)
- computeLPSArray(M, lps);
- int i = 0; // index for txt[]
- while(i < N) {
- if(pat[j] == txt[i]) {
- j++;
- i++;
- }
- if (j == M) {
- result.push(i - j);
- j = lps[j-1];
- }
- // mismatch after j matches
- else if(pat[j] != txt[i]) {
- // Do not match lps[0..lps[j-1]] characters,
- // they will match anyway
- if(j != 0)
- j = lps[j-1];
- else
- i = i+1;
- }
- }
- free(lps); // to avoid memory leak
- }
- // Driver program to test above function
- int main() {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- #endif
- int tcase, caseNo = 0, front;
- scanf("%d", &tcase);
- getc(stdin);
- while(tcase--) {
- gets(txt);
- gets(pat);
- KMPSearch();
- printf("Case %d: %d\n", ++caseNo, result.size());
- while(!result.empty()) {
- front = result.front();
- result.pop();
- printf("%d", front);
- if(result.size()) printf(" ");
- }
- putchar('\n');
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement