[UVA] 1251 - Repeated Substitution with Sed
Do you know ``sed,`` a tool provided with Unix? Its most popular use is to substitute every
occurrence of a string 
contained in the input string (actually each input line) with
another string 
. More precisely, it proceeds as follows.
- Within the input string, every non-overlapping (but possibly adjacent) occurrences of
are marked. If there is more than one possibility for non-overlapping matching, the
leftmost one is chosen.
- Each of the marked occurrences is substituted with to obtain the output string;
other parts of the input string remain intact.
For example, when is ``aa`` and is ``bca``, an input string
``aaxaaa`` will produce ``bcaxbcaa``, but not ``aaxbcaa`` nor
``bcaxabca``. Further application of the same substitution
to the string ``bcaxbcaa`` will result in ``bcaxbcbca``, but this is
another substitution, which is counted as the second one.
In this problem, a set of substitution pairs (
, 
)
(i = 1, 2,..., n), an initial string 
, and a final string 
are
given, and you must investigate how to produce from with a minimum
number of substitutions. A single substitution
(,) here means
simultaneously substituting all the non-overlapping occurrences
of
, in the sense described above, with .
You may use a specific substitution
(,) multiple times, including zero
times.
Input
The input consists of multiple datasets, each in the following format.
n
&vellip#vdots;
n is a positive integer indicating the number of pairs.
and are
separated by a single space. You may assume that
1
|| < ||10
for any i (| s| means the length of the string s),
for any
i j, n10 and
1|| < ||10. All the strings consist solely of
lowercase letters. The end of the input is indicated by a line containing a single zero.
Output
For each dataset, output the minimum number of substitutions to obtain from .
If cannot be produced from with the given set of substitutions, output `-1'.
Sample Input
2 a bb b aa a bbbbbbbb 1 a aa a aaaaa 3 ab aab abc aadc ad dee abc deeeeeeeec 10 a abc b bai c acf d bed e abh f fag g abe h bag i aaj j bbb a abacfaabe 0
Sample Output
3 -1 7 4
給定一個字串，每次使用一條規則，將字串進行轉換，問最少幾次可以達到目標字串。
替換的時候，先將第一個出現位置的地方給替換，再從上次沒替換到位置開始找尋下一個替換的位置。
利用 bfs 去找到最少步數。
#include <stdio.h>
#include <map>
#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
char a[20][20], b[20][20];
char st[20], ed[20], buf[30];
int main() {
int n;
int i, j, k;
while(scanf("%d", &n) == 1 && n) {
map<string, int> R;
for(i = 0; i < n; i++)
scanf("%s %s", &a[i], &b[i]);
scanf("%s %s", &st, &ed);
if(!strcmp(st, ed)) {
puts("0");
continue;
}
int edlen = strlen(ed);
int p, q;
queue<string> Q;
Q.push(st);
R[st] = 0;
string tn;
while(!Q.empty()) {
tn = Q.front(), Q.pop();
int step = R[tn];
for(i = 0; i < n; i++) {
//replace all a[i]->b[i]
int buflen = 0;
for(j = 0; j < tn.length(); j++) {
for(p = 0, q = j; a[i][p] && q < tn.length(); p++, q++)
if(a[i][p] != tn[q])
break;
if(a[i][p] == '\0') {
for(p = 0; b[i][p]; p++)
buf[buflen++] = b[i][p];
j = q-1;
} else
buf[buflen++] = tn[j];
if(buflen > edlen) break;
}
if(buflen > edlen) continue;
buf[buflen] = '\0';
if(R.find(buf) != R.end())
continue;
R[buf] = step+1;
Q.push(buf);
}
if(R.find(ed) != R.end())
break;
}
if(R.find(ed) == R.end())
puts("-1");
else
printf("%d\n", R[ed]);
}
return 0;
}