2013-01-21 08:25:40Morris
[UVA][字串處理] 10438 - Meta Editor
The Problem
You got a job as a programmer in the ACM (A Cool Meta-editor) company, which has has been serving as a producer of one of the coolest text editor of the world. In the update process of the text editor program of that company you are assigned a job to make a program unit which will grammatically correct a line of text. Your job is very simple, take a line of text as input and produce a line of output without the words repeated.The Input
Contains several lines of text. Each line contains several English words having no more then 50 characters each. A word may be defined as a portion of a string separated by one or more spaces or tabs. There will be no blank line in the input. A line may contain at most 20,000 characters. Input is terminated by EOF.The Output
Produce a line of text for each line of input, after removing any repeated pattern. The words must be separated by only one space.Sample Input
test string test string test string repeat repeat
Sample Output
test string repeat
這題很困難，在於理解題目內容上。
首先要找到他要 reduce 的部分，按照順序去找可以縮短的部分。
假設 substring pa, pb, A
如果存在 pa A A pb 縮成 pa A pb。
#include <stdio.h>
#include <string.h>
#define maxN 20005
char line[maxN], *token[maxN];
int main() {
while(gets(line)) {
int n = 0, i, j, k;
for(i = 0; line[i]; i++) {
if(line[i] > 32) {
token[n++] = line+i;
while(line[i] > 32)
i++;
if(line[i] == '\0')
break;
line[i] = '\0';
}
}
while(1) {
int flag = 0;
for(i = 0; i < n; i++) {
for(j = i+1; j < n; j++) {
int len = j-i; // [i...j-1],[j...j+len-1]
if(j+len-1 >= n) break;
for(k = 0; k < len; k++)
if(strcmp(token[i+k], token[j+k]))
break;
if(k == len) {
for(k = j+len, j = i+len; k < n; k++, j++)
token[j] = token[k];
flag = 1, i = j = n;
n -= len;
}
}
}
if(!flag) break;
}
for(i = 0; i < n; i++) {
if(i) putchar(' ');
printf("%s", token[i]);
}
puts("");
}
return 0;
}
再次感謝大大，大學生活少不了複製與貼上...XD