一个编程练习,该如何解决
一个编程练习
题目：http://oj.hi-hi.cn/JudgeOnline/problem.php?cid=1117&pid=2
麻烦看看能不能再源程序修改
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *getname(char name[100],char (*str)[100])
{
int i,j,k;
char a[100]={0};
for(i=0; i<5; i++)
{
//是否为同一字符串
if(strncmp(name,str[i],100) == 0)
{
continue;
}
else
{//比较第几个字符不一样
for(j=0; j<100; j++)
{
if(name[j] == str[i][j])
{
continue;
}
else
{
//复制前J个字符到a
printf("*****%d\n",j);
strncpy(a,name,j);
printf("----%s\n",a);
return a;
}
}
}
}
}
void main()
{
int i;
char str[5][100];
char (*p)[100];
char str_name[100];
p = str;
for(i=0; i<5; i++)
{
scanf("%s",p[i]);
}
for(i=0; i<5; i++)
printf("%s,%s\n",str[i],getname(str[i],str));
system("pause");
}
------解决思路----------------------
字典树裸题；
注意在oj提交代码时，别加
否则你永远别想AC。
仅供参考(AC)：
------解决思路----------------------
对于已排好序的数组，没必要这样做吧。。。
题目：http://oj.hi-hi.cn/JudgeOnline/problem.php?cid=1117&pid=2
麻烦看看能不能再源程序修改
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *getname(char name[100],char (*str)[100])
{
int i,j,k;
char a[100]={0};
for(i=0; i<5; i++)
{
//是否为同一字符串
if(strncmp(name,str[i],100) == 0)
{
continue;
}
else
{//比较第几个字符不一样
for(j=0; j<100; j++)
{
if(name[j] == str[i][j])
{
continue;
}
else
{
//复制前J个字符到a
printf("*****%d\n",j);
strncpy(a,name,j);
printf("----%s\n",a);
return a;
}
}
}
}
}
void main()
{
int i;
char str[5][100];
char (*p)[100];
char str_name[100];
p = str;
for(i=0; i<5; i++)
{
scanf("%s",p[i]);
}
for(i=0; i<5; i++)
printf("%s,%s\n",str[i],getname(str[i],str));
system("pause");
}
------解决思路----------------------
字典树裸题；
注意在oj提交代码时，别加
system("pause")
否则你永远别想AC。
仅供参考(AC)：
#include<cstdio>
#include<cstdlib>
#include<cstring>
typedef char State[42];
const int Max_N = 100000;
struct trie{
int cnt;
trie *next[32];
}*root, stack[Max_N];
int sz = 0;
State rec[110], low[110];
inline char tolow(char ch){
return ch >= 'A' && ch <= 'Z' ? ch + 32 : ch;
}
trie *_calloc(){
trie *p = &stack[sz++];
p->cnt = 0;
for (int i = 0; i < 26; i++){
p->next[i] = NULL;
}
return p;
}
void insert(trie *x, char *src){
char *p = src;
while (*p != '\0'){
if (x->next[*p - 'a'] == NULL) x->next[*p - 'a'] = _calloc();
x = x->next[*p - 'a'];
x->cnt++;
p++;
}
}
int search(trie *x, char *src){
char *p = src;
while (*p != '\0'){
if (x == NULL
------解决思路----------------------
x->next[*p - 'a'] == NULL) return 0;
x = x->next[*p - 'a'];
p++;
}
return x->cnt;
}
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
State buf, src;
int i, j, l, m, n = 0, k = 0;
root = _calloc();
while (~scanf("%s", buf)){
n = strlen(buf);
for (i = 0; i < n; i++){
low[k][i] = src[i] = tolow(buf[i]);
rec[k][i] = buf[i];
}
rec[k][i] = low[k++][i] = src[i] = '\0';
insert(root, src);
}
for (i = 0; i < k; i++){
n = strlen(rec[i]);
for (j = 0; j < n; j++){
memset(src, 0, sizeof(src));
strncpy(src, low[i], j + 1);
if (1 == search(root, src)
------解决思路----------------------
n == j + 1){
printf("%s ", rec[i]);
m = strlen(src);
for (l = 0; l < m; l++) printf("%c", rec[i][l]);
printf("\n");
break;
}
}
}
return 0;
}
------解决思路----------------------
对于已排好序的数组，没必要这样做吧。。。