首页 > 代码库 > codeforces 113 B Petr# (一道用了函数就会的题)

codeforces 113 B Petr# (一道用了函数就会的题)

2024-10-23 23:53:02   210人阅读

strncmp

strncmp函数是指定比较size个字符。也就是说，如果字符串s1与s2的前size个字符相同，函数返回值为0。此函数功能即比较字符串str1和str2的前maxlen个字符。如果前maxlen字节完全相等，返回值就=0；在前maxlen字节比较过程中，如果出现str1[n]与str2[n]不等，则依次比较str1和str2的前n位，设i(i<n)为两字符串首次的不同位，则返回（str1[i]-str2[i]）。
用了这个神函数再加上一个很水的Trie树 ，第一次发现用数组的Trie树
就是看字符串是福曾经存在，因为Trie的查找复杂度有点低，如果用map的话一个是map 的查找复杂度有点高，其实用字符串hash一样的，so   我用了trie   ，
/*************************************************************************
    > File Name: x.cpp
     > Author: wuhulala
    > Mail: xueaohui_com@163.com
    > Created Time: 2015/1/4 21:07:12
 ************************************************************************/

#include<iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

#define N 2222
char s[3000];
char b[3000],e[3000];
int ans;
int vis[N*N/2][26];
int len;
int sta1[3000];
int sta2[3000];
int lenb,lene;

void serach(int x){
	int cur =0;
	for(int i=x;s[i];i++){
		if(!vis[cur][s[i]-'a']){
			if(sta2[i]&&i>=lenb+x-1&&i>=x-1+lene) ans++;
			vis[cur][s[i]-'a']=len++;
		}
		cur=vis[cur][s[i]-'a'];
	}
}

int main(){
	scanf("%s%s%s",s,b,e);
	lenb=strlen(b);
	lene=strlen(e);
	for(int i=0;s[i];i++){
		if(!strncmp(s+i,b,lenb)) sta1[i]=1;
	    if(!strncmp(s+i,e,lene)) sta2[i+le-1]=1;
    }
    ans=0;
	len = 1;
	for(int i=0;s[i];i++)
	if(sta1[i])
	serach(i);
    cout<<ans<<endl;
}


codeforces 113 B Petr# (一道用了函数就会的题)


联系
我们