数据结构作业1-字符串

（1）-1 0 1 0 0 0 1 2 3 0
(2) -1 0 1 2 3 4 5
(3) -1 0 0 1 1 2 3 2

4.13

#include <stdio.h>
#include<iostream>
#include<string>
#include <stdlib.h> 
#include<string.h>
using namespace std;
void getnext(string p,int next[],int n){
    int i=0,j=-1;
    next[0]=-1;
    while(i<n){
           if(j==-1||p[i]==p[j]){
                  i++;
                 j++;
                   next[i]=j;//
           }
           else j=next[j];//往前回溯 
    } 
    for(i=0;i<n;i++)
        printf("%d ",next[i]);
        cout<<endl;
}
void kmp_search(string text,string pattern,int n,int m,int prefix[]){
    int i=0,j=0;//i为text的下标，j为pattern的下标 
    while(i<m){
        if(j==n-1&&text[i]==pattern[j]){
            printf("find it at %d",i-j);
            cout<<endl;
            j=prefix[j];
        }
        if(text[i]==pattern[j]||j==-1){
            i++,j++;
        }
        else {
            j=prefix[j];
        }
    }    
}
int main()
{
    string t,p;
    cout<<"请输入主串:"<<endl;
    cin>>t;
    cout<<"请输入字串:"<<endl;
    cin>>p;
    int next[1000];
    int n=p.length();
    getnext(p,next,n);
    kmp_search(t,p,p.length(),t.length(),next);
    return 0;
}

2.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void prefix_creat(char pattern[],int prefix[],int n){
        int len=0,i=1,j=0;
        prefix[0]=0;
        while(i<n){
                if(pattern[i]==pattern[j]){
                      len++;
                      prefix[i]=len;
                      i++;
                }
                else{
                    if(len>0){
                        len=prefix[len-1];
                    }
                    else {
                        prefix[i]=len;
                        i++;
                    }
                }
        }
        for(i=n-1;i>0;i--)
        prefix[i]=prefix[i-1];
        prefix[0]=-1;
}
void kmp_search(char text[],char pattern[],int n,int m,int prefix[]){
    int i=0,j=0;//i为text的下标，j为pattern的下标 
    while(i<m){
        if(j==n-1&&text[i]==pattern[j]){
            printf("find it at %d",i-j);
            j=prefix[j];
        }
        if(text[i]==pattern[j]||j==-1){
            i++,j++;
        }
        else {
            j=prefix[j];
        }
    }    
}
int main(){
    char text[100];
    printf("请输入主串:\n");
    scanf("%s",&text);
    int m=strlen(text);
    char pattern[100];
    printf("请输入字串:\n");
    scanf("%s",&pattern);
    int n=strlen(pattern);
    int prefix[100];
    prefix_creat(pattern,prefix,n);
    kmp_search(text,pattern,n,m,prefix);
} 

4.14
(1)按行优先：113
(2)按列优先：115

#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
int main(){
   string s;
   int a[1000];
   getline(cin,s);
   int len=s.length(),i=0,j=0,flag;
   while(i<len){
               int sum=0,k=10;
               flag=1;
           while(s[i]>='0'&&s[i]<='9'){
                sum=sum*k+(s[i]-'0');
                i++;
                flag=0;
           }
          if(flag) i++;
          else{
               a[j]=sum;
               j++;
          } 
   }
   for(i=0;i<j;i++)
   cout<<a[i]<<endl; 

}

#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
int main(){
   int a[1000],b[1000],c[1000],d[1000];
   cout<<"请输入数组长度:"<<endl;
   int n;
   cin>>n;
   for(int i=0;i<n;i++){
           cin>>a[i];
           b[i]=c[i]=a[i];
   }
   for(int i=1;i<n;i++)
       b[i]*=b[i-1];
    for(int i=n-2;i>=0;i--){
       c[i]*=c[i+1];
    }
    d[0]=c[1],d[n-1]=b[n-2];
    for(int i=1;i<n-1;i++){
         d[i]=b[i-1]*c[i+1];
    }
    for(int i=0;i<n;i++)
      cout<<d[i]<<' ';
}