structure.cpp

ACM经典算法ACM经典算法ACM经典算法

/*============================================================*\
 | 求某天是星期几                                             |
\*============================================================*/
char *name[] = { "monday", "tuesday", "wednesday",
"thursday", "friday", "saturday", "sunday" };
int main(void)
{
	int d, m, y, a;
	printf("Day: "); scanf("%d",&d);
	printf("Month: "); scanf("%d",&m);
	printf("Year: ");  scanf("%d",&y);
	// 1月2月当作前一年的13,14月
	if (m == 1 || m == 2) { m += 12; y--; }
	// 判断是否在1752年9月3日之前
    if ((y < 1752) || (y == 1752 && m < 9) ||
		(y == 1752 && m == 9 && d < 3))
		a = (d + 2*m + 3*(m+1)/5 + y + y/4 +5) % 7;
	else
		a = (d + 2*m + 3*(m+1)/5 + y + y/4 - y/100 + y/400)%7;
	printf("it's a %s\n", name[a]);
	return 0;
}
/*============================================================*\
 | 字符串Hash                                                 |
\*============================================================*/
unsigned int hasha(char *url, int mod)
{
	unsigned int n = 0;
    char *b = (char *) &n;
    for (int i = 0; url[i]; ++i) b[i % 4] ^= url[i];
    return n % mod;
}
unsigned int hashb(char *url, int mod)
{
	unsigned int h = 0, g;
    while (*url) {
        h = (h << 4) + *url++;
        g = h & 0xF0000000;
        if (g) h ^= g >> 24;
        h &= ~g;
    }
    return h % mod;
}
int hashc(char *p, int prime = 25013)
{
    unsigned int h=0, g;
    for ( ; *p; ++p) {
        h = (h<<4) + *p;
        if(g = h & 0xf0000000) {
            h = h ^ (g >> 24);
            h = h ^ g;
        }
    }
    return h % prime;
}
/*============================================================*\
 | KMP匹配算法                                                |
 | CALL: res = kmp(str, pat); 原串为str; 模式为pat(长度为P);  |
\*============================================================*/
int fail[P];
int kmp(char* str, char* pat)
{
	int i, j, k;
	memset(fail, -1, sizeof(fail));
	for (i = 1; pat[i]; ++i) {
		for (k=fail[i-1]; k>=0 && pat[i]!=pat[k+1]; k=fail[k]);
		if (pat[k + 1] == pat[i]) fail[i] = k + 1;
	}
	for (i = 0; str[i]; j = fail[j] + 1) {
		for (j = 0; pat[j]; ++j, ++i)
			if (str[i] != pat[j]) { ++i; break; }
		if (0 == pat[j]) return i - j;
	}
	return -1;
}
/*============================================================*\
 | Karp-Rabin字符串匹配                                       |
 | hash(w[0..m-1])=(w[0] * 2^(m-1) + ... + w[m-1] * 2^0) % q; |
 | hash(w[j+1..j+m])=rehash(y[j], y[j+m], hash(w[j..j+m-1]);  |
 | rehash(a, b, h) = ((h - a * 2^(m-1) ) * 2 + b) % q;        |
 | 可以用q = 2^32简化%运算                                    |
\*============================================================*/
#define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))
int krmatch(char *x, int m, char *y, int n)
{	// search x in y
	int d, hx, hy, i, j;
	for (d = i = 1; i < m; ++i) d = (d<<1);
	for (hy = hx = i = 0; i < m; ++i) {
		hx = ((hx<<1) + x[i]); hy = ((hy<<1) + y[i]);
	}
	for (j = 0; j <= n - m; ++j) {
		if (hx == hy && memcmp(x, y + j, m) == 0) return j;
		hy = REHASH(y[j], y[j + m], hy);
	}
}
/*============================================================*\
 | 基于Karp-Rabin的字符块匹配                                 |
 | Text: n * m matrix;  Pattern: x * y matrix;                |
\*============================================================*/
#define uint unsigned int
const int A=1024, B=128;
const uint E=27;
char text[A][A], patt[B][B];
uint ht, hp, pw[B * B], hor[A], ver[A][A];
int n, m, x, y;
void init()
{
	int i, j = B * B;
	for (i=1, pw[0]=1; i<j; ++i) pw[i] = pw[i-1] * E;
}
void hash()
{
	int i, j;
	for (i=0; i<n; ++i) for (j=0, hor[i]=0; j<y; ++j) {
		hor[i]*=pw[x]; hor[i]+=text[i][j]-'a';
	}

	for (j=0; j<m; ++j) {
		for (i=0, ver[0][j]=0; i<x; ++i) {
			ver[0][j]*=E; ver[0][j]+=text[i][j]-'a';
		}
		for (i=1 ; i<=n-x; ++i)
			ver[i][j]=
			(ver[i-1][j]-(text[i-1][j]-'a')*pw[x-1])*E
			+text[i+x-1][j]-'a';
	}
	for (j=0, ht=hp=0; j<y; ++j) for (i=0; i<x; ++i) {
		ht*=E; ht+=text[i][j]-'a';
		hp*=E; hp+=patt[i][j]-'a';
	}
}
void read()
{
	int i;
	scanf("%d%d", &n, &m);
	for (i=0; i<n; ++i) scanf("%s", text[i]);
	scanf("%d%d", &x, &y);
	for (i=0; i<x; ++i) scanf("%s", patt[i]);
}
int solve()
{
	if (n==0||m==0||x==0||y==0) return 0;
	int i, j, cnt=0; uint t;
	for (i=0; i<=n-x; ++i) {
		for (j=0, t=ht; j<=m-y; ++j) {
			if (t==hp) ++cnt;
			t=(t-ver[i][j]*pw[y*x-x])*pw[x]+ver[i][j+y];
		}
		ht=(ht-hor[i]*pw[x-1])*E+hor[i+x];
	}

	return cnt;
}
int main(void)
{
	int T; init();
	for (scanf("%d", &T); T; --T) {
		read(); hash();
		printf("%d\n", solve());
	}
	return 0;
}
/*============================================================*\
 | 左偏树 合并复杂度O(log N)                                  |
 | INIT: init()读入数据并进行初始化;                          |
 | CALL: merge() 合并两棵左偏树; ins() 插入一个新节点;        |
 |       top() 取得最小结点; pop() 取得并删除最小结点;        |
 |       del() 删除某结点; add() 增/减一个结点的键值;         |
 |       iroot() 获取结点i的根;                               |
\*============================================================*/
#define typec int              // type of key val
const int na = -1;
struct node { typec key; int l, r, f, dist; } tr[N];
int iroot(int i)               // find i's root
{
	if (i == na) return i;
    while (tr[i].f != na) i = tr[i].f;
    return i;
}
int merge(int rx, int ry)     // two root: rx, ry
{
    if (rx == na) return ry;
    if (ry == na) return rx;
    if (tr[rx].key > tr[ry].key) swap(rx, ry);
    int r = merge(tr[rx].r, ry);
    tr[rx].r = r; tr[r].f = rx;
    if (tr[r].dist > tr[tr[rx].l].dist)
        swap(tr[rx].l, tr[rx].r);
    if (tr[rx].r == na) tr[rx].dist = 0;
    else tr[rx].dist = tr[tr[rx].r].dist + 1;
    return rx;                // return new root
}
int ins(int i, typec key, int root) // add a new node(i, key)
{
    tr[i].key = key;
    tr[i].l = tr[i].r = tr[i].f = na;
    tr[i].dist = 0;
    return root = merge(root, i);  // return new root
}
int del(int i)            // delete node i
{
	if (i == na) return i;
    int x, y, l, r;
    l = tr[i].l; r = tr[i].r; y = tr[i].f;
    tr[i].l = tr[i].r = tr[i].f = na;
    tr[x = merge(l, r)].f = y;
    if (y != na && tr[y].l == i) tr[y].l = x;
    if (y != na && tr[y].r == i) tr[y].r = x;
    for ( ; y != na; x = y, y = tr[y].f) {
        if (tr[tr[y].l].dist < tr[tr[y].r].dist)
            swap(tr[y].l, tr[y].r);
        if (tr[tr[y].r].dist + 1 == tr[y].dist) break;
        tr[y].dist = tr[tr[y].r].dist + 1;
    }
	if (x != na) return iroot(x); // return new root
	else return iroot(y);
}
node top(int root)
{
    return tr[root];
}
node pop(int &root)
{
    node out = tr[root];
    int l = tr[root].l, r = tr[root].r;
    tr[root].l = tr[root].r = tr[root].f = na;
    tr[l].f = tr[r].f = na;
    root = merge(l, r);
    return out;
}
int add(int i, typec val)  // tr[i].key += val
{
	if (i == na) return i;
	if (tr[i].l == na && tr[i].r == na && tr[i].f == na) {
		tr[i].key += val;
		return i;
	}
	typec key = tr[i].key + val;
	int rt = del(i);
	return ins(i, key, rt);
}
void init(int n)
{
	for (int i = 1; i <= n; i++) {
		scanf("%d", &tr[i].key); //%d: type of key
		tr[i].l = tr[i].r = tr[i].f = na;
		tr[i].dist = 0;
	}
}
/*============================================================*\
 | 树形数组                                                   |
 | INIT: ar[]置为0;                                           |
 | CALL: add(i, v): 将i点的值加v;    sum(i): 求[1, i]的和;    |
\*============================================================*/
#define typev int                   // type of res
typev ar[N];                        // index: 1 ~ N-1
int lowb(int t) { return t & (-t) ; }
void add(int i, typev v) {
	for ( ; i < N; ar[i] += v, i += lowb(i));
}
typev sum(int i) {
	typev s = 0;
	for ( ; i > 0; s += ar[i], i -= lowb(i));
	return s;
}
/*============================================================*\
 | Trie树(k叉)                                                |
 | INIT: init();                                              |
 | 注: tree[i][tk] > 0时表示单词存在, 当然也可赋予它更多含义; |
\*============================================================*/
const int tk = 26, tb = 'a';  // tk叉; 起始字母为tb;
int top, tree[N][tk + 1];     // N: 最大结点个数
void init()
{
	top = 1;
	memset(tree[0], 0, sizeof(tree[0]));
}
int sear(char *s) // 失败返回0
{
	for (int rt = 0; rt = tree[rt][*s - tb]; )
		if (*(++s) == 0) return tree[rt][tk];
	return 0;
}
void insert(char *s, int rank = 1)
{
	int rt, nxt;
	for (rt = 0; *s; rt = nxt, ++s) {
		nxt = tree[rt][*s - tb];
		if (0 == nxt) {
			tree[rt][*s - tb] = nxt = top;
			memset(tree[top], 0, sizeof(tree[top]));
			top++;
		}
	}
	tree[rt][tk] = rank;
}
void delt(char *s) // 只做标记, 假定s一定存在
{
	int rt = 0;
	for ( ; *s; ++s) rt = tree[rt][*s - tb];
	tree[rt][tk]=0;
}
int profix(char *s) // 最长前缀
{
	int rt = 0, lv;
	for (lv = 0; *s; ++s, ++lv) {
		rt = tree[rt][*s - tb];
		if (rt == 0) break;
	}
	return lv;
}
/*============================================================*\
 | Trie树(左儿子又兄弟)                                       |
 | INIT: init();                                              |
\*============================================================*/
int top;
struct trie { char c; int l, r, rk; } tree[N];
void init()
{
	top = 1;
	memset(tree, 0, sizeof(tree[0]));
}
int sear(char *s)                // 失败返回0
{
	int rt;
	for (rt = 0; *s; ++s) {
		for (rt = tree[rt].l; rt; rt = tree[rt].r)
			if (tree[rt].c == *s) break;
		if (rt == 0) return 0;
	}
	return tree[rt].rk;
}
void insert(char *s, int rk = 1) //rk: 权或者标记
{
	int i, rt;
	for (rt = 0; *s; ++s, rt=i) {
		for (i = tree[rt].l; i; i = tree[i].r)
			if (tree[i].c == *s) break;
		if (i == 0) {
			tree[top].r = tree[rt].l;
			tree[top].l = 0;
			tree[top].c = *s;
			tree[top].rk = 0;
			tree[rt].l = top;
			i = top++;
		}
	}
	tree[rt].rk=rk;
}
void delt(char *s)   // 假定s已经存在, 只做标记
{
	int rt;
	for (rt = 0; *s; ++s) {
		for (rt = tree[rt].l; rt; rt = tree[rt].r)
			if (tree[rt].c == *s) break;
	}
	tree[rt].rk = 0;
}
int profix(char *s)  // 最长前缀
{
	int rt = 0, lv;
	for (lv = 0; *s; ++s, ++lv) {
		for (rt = tree[rt].l; rt; rt = tree[rt].r)
			if (tree[rt].c == *s) break;
		if (rt == 0) break;
	}
	return lv;
}
/*============================================================*\
 | 后缀数组 O(N * log N)                                      |
 | INIT: n = strlen(s) + 1;                                   |
 | CALL: makesa(); lcp();                                     |
 | 注: height[i] = lcp(sa[i], sa[i-1]);                       |
\*============================================================*/
char s[N];                          // N > 256
int n, sa[N], height[N], rank[N], tmp[N], top[N];
void makesa()                       // O(N * log N)
{