在串字符的外观

Question

给定字符的S串，写一个程序，响应正确如果角色C出现在S的开始于位置I和具有长度T的子串

条目 至多百万的字母数字字符和长度的S-串形成。接着一个整数n接着加入N三联体C，I，T。可以假定认为1≤N≤10,0000≤I<| S |和1≤T≤| S | -一世。

出口 对于每一个问题，如果该字符出现在所指示的子串，否则为0与1的线。

我的想法是实现二进制搜索，但有资格它说，它超越预期的时间，我不知道如何把它优化到法官接受我的算法程度的判断。例如，一个条目可以是：

how are you
3
h 0 3
1
o 2 5
1
a 4 4
0 

我的代码：

#include <stdio.h>
#include <string.h>

int busqcadena(char cadena[], int a[],char x,int pos,int n);

int main()
{
    char cadena[1000000]; 
    char c;
    int t = 0, i; 
    int pos, lon, a[1000000], j = 0;
    do{
        fflush(stdin);
        c = getchar();
        cadena[i++] = c;
        a[j] = j;
        j++;
    } while (c != '\n');
    cadena[ i - 1 ] = '\0'; 

    scanf("%d",&t);
    for( int k = 0; k < t; k++){
    char pa; pos = 0; lon = 0;
    scanf("%s %d %d",&pa, &pos, &lon);
    int busq3 = busqcadena(cadena,a,pa,pos,lon);
    if( busq3 != -1){
        printf("1\n");
    }else{
        printf("0\n");
    } 
}
    return 0; 
}

int busqcadena(char cadena[], int arr[],char x,int pos,int n){
    int a = 0, b = n - 1;
    while( a <= b ){
        int k = (a+b)/2;
        if( cadena[k] == x && arr[k] == pos){
            return arr[k]; 
        }
        if( arr[k] > pos ) b = k - 1;
        else a = k + 1;
    }
    return -1;
}

Answer 1

既然你只有固定的字符数就可以计算出每个人物从指数0开始计数。一旦你这样做，你只需要检查次数增加从Ito T该字符。伪代码如下

char_count = 26 # I am assuming only lower case letter, but change it if its not
max_len = 1000000  # maximum length of string
count = int[char_count][max_len]  # 2D array storing cumulative count for each character, fill with 0

# read the string s
# populate the count array
count[s[0]][0] = 1  # set count 1 for first character in S
for i=0:char_count:
    for j=1:len(s):
        if s[j] == char[i]:  # equals i-th character
            count[i][j] = count[i][j-1]+1
        else:
            count[i][j] = count[i][j-1]

# for each query do following 
for q=0:num_queries:
    if count[C][T] != count[C][I]:
        print(1)
    else:
        print(0)