cjang
BAN USERSimilar approach to Rabin-Karp string search algorithm.
// prime number based hash.
#define PRIME 103
uint64_t hash(const char *s, int len)
{
uint64_t h = 0;
for (int i = 0; i < len; ++i) {
h = h*PRIME + s[i];
}
return h;
}
int findAnagram(const char *A, const char *B, char *T)
{
int A_len = strlen(A);
int B_len = strlen(B);
if (A_len > B_len) {
return B_len;
}
// PRIME^(A_len-1)
uint64_t P = 1;
for (int i = 1; i < A_len; ++i) Hk *= PRIME;
// get hash value of input string.
uint64_t H = hash(A, A_len);
uint64_t h = hash(B, A_len);
for (int i = 0; i < (B_len - A_len); ++i) {
if (H == h) {
strncpy(T, B+i, A_len);
std::sort(T, T+A_len);
if (strncmp(A, T, A_len) == 0) {
return i;
}
}
h = h - B[i] * P + B[i+A_len];
}
return B_len;
}
Assume that A is already sorted. When a substring of B shows the same hash value with A, the substring is copied to T and compared one-by-one after being sorted. The time complexity will be O(n + c*m*logm) where n is length of B, m is length of A, and c is the number of false positive cases.
- cjang March 28, 2014
Suppose that a graph has been constructed as follows:
- All nodes are ordered by its value.
- Each node has an sorted list of edges.
- An edge belongs to only at a single node with less value among two nodes.
For example, the above graph will be represented by
0: {1, 2}
1: {2, 4}
2: {}
4: {}
Then, the number of triangles can be obtained by counting the number of common nodes between every pair of nodes (n0, n1) where n0 < n1.
The time complexity of this algorithm consists of two parts. First, constructing the graph will be inserting each edge to the proper node. Each insertion of an edge takes O(E/N). (Assume that the number of edges connected for each node is even). So, graph construction takes O(E*log(E/N)).
- cjang March 31, 2014Second, counting the number of triangles takes O(N * E/N * E/N). The outer loop and inner loop iterate N and E/N times, respectively, and countIntersection takes O(E/N).
If we assume dense graph, i.e., E=O(N^2), then the time complexity is O(N^3). If it is sparse, i.e., E=O(N), then O(N).