# Tag Info

Accepted

### Finding the number of square prefixes of a string in linear time

Suppose there is an $O(|W|)$ algorithm that computes a slightly different prefix function: $Z[i]$ is the longest prefix of $W$ that is also a prefix of $W[i..n]$. Note then that your answer will ...
Accepted

### Counting specific subgraphs

Your problem is known as counting the number of connected spanning subgraphs, and is pretty hard even for restricted classes of graphs. See this question on cstheory. The number of connected spanning ...
Accepted

### Counting islands in Boolean matrices

Here's a sketch of an algorithm that only keeps two rows in memory at a time, so $O(m)$ memory. But since you can run this algorithm on the transpose of the matrix without issues, the actual ...
Accepted

### Count numbers less than $K$ in array

Here is a $O(1)$ solution after $O(n)$ preprocessing step, assuming that all elements are less than some number $C$ (in your case $10^5$) in pseudocode ...
Accepted

### Counting on a matrix

Copied from here. The mathematics Consider the group $G=S_w\times S_h$, where $S_w$ and $S_h$ are the symmetric group of the sets $W=\{1,2,3,\ldots,w\}$ and $H=\{1,2,3,\ldots,h\}$ with $w$ and $h$ ...

### How is the set of functions from ${\{a,b\}}$ to $N$ countable?

You are confusing countable and finite. A finite set is always countable, however a countable set can be infinite. You only need to find an injection from your set and $\mathbb{N}$, it means that ...