 # SUBSTR - Editorial

Easy

### PROBLEM

Given an integer N, let SN be the string formed by concatenating all the integers between 1 and N, inclusive.

Thus, S20 = 1234567891011121314151617181920

Given an integer K, find the number of times K appears as a substring of N.

### EXPLANATION

This problem was intended to be trivial. A lot of doubts were raised about how many test cases were crunched into a file, but all such questions were intentionally left unanswered.

See, the real limit on T was defined in the problem statement, cheekily, as a limit on sum of N across all test cases in a file. This limit was 1,000,000. An algorithm of the order of O(N) will not take more than O(sum(N)) for a test file. In fact, solutions with complexity O(N log10 K) will pass as well.

The following python-code will solve the problem. (C like code snippets are in the next section)

```import re
T = int(raw_input())
for _ in xrange(T):
N, K = raw_input().split()
S = "".join(map(str,range(1,int(N)+1)))
R = [m.start() for m in re.finditer('(?='+K+')', S)]
print len(R)
```

If only ICPC rules allowed languages besides C/C++ and JAVA!

### CODE COMMENTARY

The problem can be solved by generating the entire string SN for each test case. To achieve faster times, once can pre-compute the string S1000000 and then store the last-indices, up to which the checks should be performed.

The following C-code is enough to solve the problem. It is almost equivalent to the python code above.

```char A;
int main() {
char K, nk;
int T, N, t = 0, result = 0;
scanf("%d",&T);
while(T--) {
scanf("%d %s",&N,K);
nk = strlen(K);
t = 0; for(int i=1;i<=N;i++) t += sprintf(A+t, "%d", i);
result = 0; for(int i=0;i<t;i++) result += !strncmp(K,A+i,nk);
printf("%d
",result);
}
}
```

Check the tester’s solution for an approach that pre-computes S1000000.

Can be here

Can be here

8 Likes