1627 - 子串计算

1010100001
1010

0 6
00 3
000 2
01 3
010 2
1 4
10 3
101 2
1010 2
0 2
1 2
10 2

提示

	字符串前缀查找

C语言解答

#include "stdio.h"
#include "math.h"
#include "stdlib.h"
#include "string.h"
 
typedef struct{
    char ch[101];
    int value2;
    struct Node *left;
    struct Node *right;
}Node,*BiTree;
 
void insert(BiTree *b,char *ch2);
void find (BiTree b,char *ch,BiTree *b2);
void print (BiTree b);
char * copy (char *des,char *src,int start,int end);
void destroy (BiTree *b);
 
int main () {
    char ch[101];
    char ch2[101];
    BiTree b = NULL;
     
    int i,j,length;
    while (scanf ("%s",ch)!=EOF) {
        length = strlen (ch);
        for (i = 1;i <=length;i++){
            for (j = 0;j < length;j++) {
                if (j + i <= length) {
                    copy (ch2,ch,j,j+i);
                    insert (&b,ch2);
                }
                 
            }
        }
        print(b);
    destroy(&b);
    }
 
    return 0;
}
 
 
void insert (BiTree *b,char *ch2) {
    if (*b == NULL) {
        (*b) = (BiTree)malloc(sizeof(Node));
        strcpy((*b)->ch,ch2);
        (*b)->value2 = 1;
        (*b)->left = (*b)->right = NULL;
    }else {
        BiTree b2,b3;
        find (*b,ch2,&b2);
        if (b2 !=NULL) {
            b3= (BiTree)malloc(sizeof (Node));
             b3->left = b3->right = NULL;
             b3->value2 = 1;
            strcpy((b3)->ch,ch2);
            if (strcmp (b2->ch,ch2) > 0) {
                b2->left =  b3;
            }else {
                b2->right = b3;
            }
        }
    }
}
 
 
void find (BiTree b,char *ch,BiTree *b2) {
    if (b == NULL) {
        return;
    }else {
        if (strcmp(b->ch,ch) == 0) {
            b->value2++;
            *b2 = NULL;
            return;
        }else if (strcmp (b->ch,ch) > 0 ) {
            *b2 = b;
            find (b->left,ch,b2);
        }else {
            *b2 = b;
            find (b->right,ch,b2);
        }
    }
}
 
 
 
void print (BiTree b) {
    if (b == NULL) {
        return;
    }else {
        print(b->left);
        if (b->value2 >1) {
          printf("%s %d\n",b->ch,b->value2);
        }
         
        print(b->right);
    }
}
 
 
char * copy (char *des,char *src,int start,int end) {//不包括end的值
    int index = 0;
    for (;start < end;start++) {
        des[index++] = src[start];
    }
    des[index] = '\0';
}
 
void destroy (BiTree *b) {
    free(*b);
    *b= NULL;
}

C++解答

#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
struct Sc {
 
    string s;
 
    int cnt;
 
    Sc(){};
 
    Sc(string ss , int icnt):s(ss),cnt(icnt){};
 
};
 
int cmp (const Sc& a,const Sc& b){
 
    return a.s<b.s;
 
}
 
// 在字符串s中找字符串sub，结果存入v
 
void find (string s, string sub,vector<Sc>&v){
 
    int cur=0,cnt = 0;
 
    while(1){
 
        int next = s.find(sub,cur);
 
        if(next !=string::npos){
 
            cnt++ ;
 
            cur= next+1;
 
        }
 
        else break;
 
    }
 
    if(cnt>1) v.push_back(Sc(sub,cnt));
 
}
 
int main ()
{
    //freopen("in.txt","r",stdin);
    string s;
    while(cin >> s)
    {
 
        vector<Sc>strs;
 
        int len = s.length();
 
        int i,j,k;
 
        for(i=0;i<len;i++)
        {
 
            for(j=1;j<=len-i;j++)
            {
 
                string cur = s.substr(i,j);  // 注意substr的参数：开始位置和长度。
 
                find(s,cur,strs);
 
            }
 
        }
 
        sort(strs.begin(),strs.end(),cmp);
 
 
        for(k=0;k<strs.size();k+=strs[k].cnt)
        {
 
            cout<< strs[k].s <<" "<< strs[k].cnt << endl;
 
        }
 
    }
 
    return 0;
}