字符串ACM模板.doc

字符串 KMP #includeiostream using namespace std; char t[10010],s[1000100]; int kmpNext[10010]; /* standard C code for KMP */ void preKmp(char *x, int m, int kmpNext[]) { int i, j; i = 0; j = kmpNext[0] = -1; while (i m) { while (j -1 x[i] != x[j]) { j = kmpNext[j]; } i++; j++; if (x[i] == x[j]) { kmpNext[i] = kmpNext[j]; } else { kmpNext[i] = j; } } } int KMP(char *x, int m, char *y, int n) { int i,j,tot=0; /* Preprocessing */ preKmp(x, m, kmpNext); /* Searching */ i = j = 0; while (j n) { while (i -1 x[i] != y[j]) { i = kmpNext[i]; } i++; j++; if (i = m) { //OUTPUT(j - i); /* found one, do next if required*/ tot++; i = kmpNext[i]; } } return tot; } int main() { int T; //freopen(in.txt,r,stdin); scanf(%d\n,T); while(T--) { gets(t); gets(s); printf(%d\n,KMP(t,strlen(t),s,strlen(s))); } return 0; } 通配符匹配 int wildcard(const char * pat, const char * str) { while(*str *pat) { if(*pat==?) { if(wildcard(pat+1, str+1)) return 1; str++; pat++; } else if(*pat==*) { while(*pat==*) pat++; if(!*pat) return 1; while(*str) { if(wildcard(pat, str)) return 1; str++; } return 0; } else { if(*pat!=*str) return 0; str++; pat++; } } if(*str!=0) return 0; while(*pat==*) pat++; return !*pat; } 最小表示法 说把一个长为len的字符串围成一个圈，然后从任意一个字符作为起点顺时针转，都会产生一个新的长为len字符串，现在要求所有的可以产生的字符串中字典序最小的那个。下面这个函数就是解决这个问题的，返回值即为从原串中这个位置起产生的串就是字典序最小的。 int MinimumRepresentation(char *s, int l) { int i = 0, j = 1, k = 0, t; while (i l j l k l) { t = s[(i + k)%l] - s[(j + k)%l]; if (!t) ++ k; else {