首页 > 试题广场 >

最强大脑

[编程题]最强大脑
  • 热度指数：538 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
人脑对于长度特别长的字符串的处理速度是有限的，但是最强大脑挑战的就是人脑的极限，现在有这样一项挑战，给出一个很长的字符串S，和一个较短的字符串T，请你求出对于每一个前缀[1,r]内有多少个T字符串。

输入描述:
第一行一个字符串S。
第二行一个字符串T。两个字符串保证均只含小写字母。（1≤|S|≤500000, 1≤|T|≤100）


输出描述:
输出仅包含|S|个正整数，分别表示[1,r]内有多少个T字符串。(1<=r<=|S|)
示例1

输入

ababac
ab

输出

0 1 1 2 2 2
算法知识视频讲解
添加回答
filter一切头像 filter一切 
var p=readline();
var r=readline();
let str;
let sum=0;
let result=new Array(r.length-1).fill(0);
for(var i=0,j=r.length;j<=p.length;i++,j++){
    if(p.slice(i,j)==r){
        sum+=1;
        result.push(sum);
    }else{
        result.push(sum);
    }
}
console.log(result.join(' '))
双指针法

发表于 2020-05-27 19:40:39 回复(1)
这个昵称与你无缘头像 这个昵称与你无缘
kmp算法，vec中保存S串中包含的所有T串的结尾位置，如S串为ababa，T串为ab，那么vec中应该保存1和3，这样对于S中的每一位i，判断有多个vec[i]<=i即可。 
#include <bits/stdc++.h>

using namespace std;

#define ll long long int
#define angel 0x3f3f3f3f
#define maxn 500005
#define pb push_back

const ll mod=1000000007;
char str[maxn];
char p[105];
int NEXT[105];
vector<int>vec;
void GetNEXT()
{
	int pLen = strlen(p);
	NEXT[0] = -1;
	int k = -1;
	int j = 0;
	while (j < pLen - 1)
	{
		//p[k]表示前缀，p[j]表示后缀
		if (k == -1 || p[j] == p[k])
		{
			++k;
			++j;
			NEXT[j] = k;
		}
		else
		{
			k = NEXT[k];
		}
	}
}
void Find()
{
    int slen=strlen(str);
    int plen=strlen(p);
    int m=0,n=0;
    while(m<slen)
    {
        if(str[m]==p[n]||n==-1)
        {
            m++;
            n++;
            if(n==plen)
            {
                vec.pb(m-1);
                n=0;
                m=m-plen+1;
            }
        }
        else
            n=NEXT[n];
    }
}
int main()
{
    scanf("%s",str);
    scanf("%s",p);
    GetNEXT();
    Find();
    int size=vec.size();
    int len=strlen(str);
    int now=0;
    int cnt=0;
    for(int i=0;i<len;i++)
    {
        if(now<len&&i==vec[now])
        {
            now++;
            cnt++;
        }
        if(i!=0)
            printf(" ");
        printf("%d",cnt);

    }
    return 0;
}
/*
5
54 125 2 52 128
*/



发表于 2020-09-20 15:03:46 回复(0)
pein531头像 pein531
当S子串的长度小于字符串T的长度时输出0，当子串长度超过T的长度时需要判断S是否是以T结尾的，如果是，计数自增，否则不变 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        String T = br.readLine();
        int slen = S.length();
        int tlen = T.length();
        int count = 0;
        for(int r = 1; r <= slen; r++){
            if(r < tlen)
                System.out.print(count + " ");
            else{
                if(S.substring(r - tlen, r).equals(T))
                    count ++;
                System.out.print(count + " ");
            }
        }
    }
}


发表于 2020-12-10 10:20:25 回复(0)
六娃lw头像 六娃lw
经典KMP算法，字符串匹配问题。 
import java.util.*;
import java.io.*;

public class Main {
    
    private static int[] getNext(char[] cs){
        int len = cs.length, j = -1;
        int[] next = new int[len];
        next[0] = -1;
        for(int i = 1; i < len; ++i){
            while(j != -1 && cs[i] != cs[j + 1]){j = next[j];}
            if(cs[i] == cs[j + 1]){++j;}
            next[i] = j;
        }
        return next;
    }
    
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String S = scan.nextLine(), T = scan.nextLine();
        char[] charS = S.toCharArray(), charT = T.toCharArray(); 
        int m = S.length(), n = T.length();
        int[] next = getNext(charT);
        int count = 0;
        int j = -1;
        for(int i = 0; i < m; ++i){
            while(j != -1 && charS[i] != charT[j + 1]){j = next[j];}
            if(charS[i] == charT[j + 1]){++j;}
            if(j == n - 1){
                ++count;
                j = next[j];
            }
            System.out.print(count + " ");
        }
    }
}


发表于 2020-11-14 19:37:03 回复(0)
牛客577957613号头像 牛客577957613号 
import sys

def countsubstr(s, t):
    pre = 0
    ans = []
    for i in range(len(s)):
        if i >= len(t) - 1:
            if s[i-len(t)+1:i+1] == t:
                pre += 1
        ans.append(pre)
    return ans


if __name__ == '__main__':

    lines = sys.stdin.readlines()
    if len(lines) == 1:
        s = lines[0].strip()
        t = ''
    else:
        s = lines[0].strip()
        t = lines[1].strip()

    if len(t) > len(s):
        for i in range(len(s)):
            print(0, end=' ')
    elif not t&nbs***bsp;len(t) == 0:
        for i in range(len(s)):
            print(0, end=' ')
    else:
        ans = countsubstr(s, t)
        for i in range(len(s)):
            print(ans[i], end=' ')
一开始没懂题目意思，实际上，s中包含的t串可以有重叠
发表于 2020-04-18 19:23:45 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 爱奇艺 2020 Java工程师
上传者：小小
难度：
5条回答 3353浏览

热门推荐

通过挑战的用户

相关试题

最强大脑

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号