福州大学算法作业题 - 最长子串

★实验任务

给你一个长度为 n 的数组，现在需要求出异或和为零的最长连续子串。 一个子串的异或和指的是将子串中所有的数异或起来得到的值，比如给定 {1,1,2,2}，异或和为零的连续子串有{1,1},{2,2},{1,1,2,2}。其中最长的连续 子串为{1,1,2,2}。 

★数据输入

输入数据占两行，第一行输入一个正整数 n，第二行输入 n 个非负整数，任 意两个数之间由空格隔开。 

★数据输出

输出三个整数 l、s、t 分别代表子串的长度以及子串的左右端点坐标(数组 下标从 1 开始），如果存在多解，则输出 s 值最小的解。 如果不存在这样的子串，则只需要输出一个-1。 

★数据范围

50%的得分点，n<=100； 80%的得分点，n<=1000； 100%的得分点，n<=100000。 n 个整数取值范围在 int 范围内。

代码1：

#include <stdio.h>  
#include <map>  
using namespace std;    
int main(){  
    int n;  
    scanf("%d", &n);  
    int * a = new int[n];  
    int i;  
    for(i=0;i<n;i++){  
        scanf("%d", &a[i]);  
    }  
    map<int,int> m;  
    m[0] = -1;  
    map<int , int>::iterator ite;  
    int con = 0;  
    int l=-1,s=1,t=1;  
    int tl;  
    for(i=0;i<n;i++){  
        con^=a[i];  
        ite = m.find(con);   
        if( ite != m.end() ){  
            tl = i - ite->second;  
            if(tl > l){  
                l = tl;  
                s = ite->second+2;  
                t = i+1;  
            }  
        }else{  
            m[con] = i;  
        }  
    }  
    if(l == -1){  
        printf("%d", l);  
    }else{  
        printf("%d %d %d", l, s, t);  
    }  
    return 0;  
}  

 代码2：

#include<iostream>  
#include<cstdio>  
#include<map>  
using namespace std;  
  
map<int,int> tag;  
int num[100005];  
int main(){  
    int n,i,length,start,end;  
    start = end =-1;  
    length=-1;  
    tag[0]=0;  
    num[0]=0;  
    scanf("%d",&n);  
    for(i=1;i<=n;i++){  
        scanf("%d",&num[i]);  
        num[i]=num[i-1]^num[i];  
        if(tag.find(num[i])==tag.end()){  
            tag[num[i]]=i;  
        }  
        else{  
            if(i-tag[num[i]]>length){  
                length=i-tag[num[i]];  
                start=tag[num[i]]+1;  
                end=i;  
            }  
        }  
    }  
    if(length==-1){  
        printf("%d\n",-1);  
    }  
    else{  
        printf("%d %d %d\n",length,start,end);  
    }  
    return 0;  
}  

代码3：

#include<iostream>  
#include<map>  
#include<cstdio>  
using namespace std;  
int n, l=-1, s, e;  
int total = 0, tmp;  
map<int, int> m;  
  
int main(){  
    int i;  
    scanf("%d", &n);  
    for(i=1; i<=n; i++){  
        scanf("%d", &tmp);  
        total = total ^ tmp;  
        if(total == 0){  
            l = i; s = 1; e = i;  
        }  
        // 不为0就一直记录，为零单独考虑，存一个最开始total为0的节点   
        else{  
            if(m.find(total) == m.end())  
                m[total] = i;  
            else{  
                if(i - m[total] > l){  
                    l = i - m[total];  
                    s = m[total] + 1;  
                    e = i;  
                }  
            }   
        }  
    }  
    if(l > 0)  
        printf("%d %d %d\n", l, s, e);  
    else  
        printf("-1\n");  
    return 0;   
}