Metamath Proof Explorer


Theorem swrdspsleq

Description: Two words have a common subword (starting at the same position with the same length) iff they have the same symbols at each position. (Contributed by Alexander van der Vekens, 7-Aug-2018) (Proof shortened by AV, 7-May-2020)

Ref Expression
Assertion swrdspsleq W Word V U Word V M 0 N 0 N W N U W substr M N = U substr M N i M ..^ N W i = U i

Proof

Step Hyp Ref Expression
1 swrdsb0eq W Word V U Word V M 0 N 0 N M W substr M N = U substr M N
2 1 3expa W Word V U Word V M 0 N 0 N M W substr M N = U substr M N
3 2 ancoms N M W Word V U Word V M 0 N 0 W substr M N = U substr M N
4 3 3adantr3 N M W Word V U Word V M 0 N 0 N W N U W substr M N = U substr M N
5 ral0 i W i = U i
6 nn0z M 0 M
7 nn0z N 0 N
8 fzon M N N M M ..^ N =
9 6 7 8 syl2an M 0 N 0 N M M ..^ N =
10 9 biimpa M 0 N 0 N M M ..^ N =
11 10 raleqdv M 0 N 0 N M i M ..^ N W i = U i i W i = U i
12 5 11 mpbiri M 0 N 0 N M i M ..^ N W i = U i
13 12 ex M 0 N 0 N M i M ..^ N W i = U i
14 13 3ad2ant2 W Word V U Word V M 0 N 0 N W N U N M i M ..^ N W i = U i
15 14 impcom N M W Word V U Word V M 0 N 0 N W N U i M ..^ N W i = U i
16 4 15 2thd N M W Word V U Word V M 0 N 0 N W N U W substr M N = U substr M N i M ..^ N W i = U i
17 swrdcl W Word V W substr M N Word V
18 swrdcl U Word V U substr M N Word V
19 eqwrd W substr M N Word V U substr M N Word V W substr M N = U substr M N W substr M N = U substr M N j 0 ..^ W substr M N W substr M N j = U substr M N j
20 17 18 19 syl2an W Word V U Word V W substr M N = U substr M N W substr M N = U substr M N j 0 ..^ W substr M N W substr M N j = U substr M N j
21 20 3ad2ant1 W Word V U Word V M 0 N 0 N W N U W substr M N = U substr M N W substr M N = U substr M N j 0 ..^ W substr M N W substr M N j = U substr M N j
22 21 adantl ¬ N M W Word V U Word V M 0 N 0 N W N U W substr M N = U substr M N W substr M N = U substr M N j 0 ..^ W substr M N W substr M N j = U substr M N j
23 swrdsbslen W Word V U Word V M 0 N 0 N W N U W substr M N = U substr M N
24 23 adantl ¬ N M W Word V U Word V M 0 N 0 N W N U W substr M N = U substr M N
25 24 biantrurd ¬ N M W Word V U Word V M 0 N 0 N W N U j 0 ..^ W substr M N W substr M N j = U substr M N j W substr M N = U substr M N j 0 ..^ W substr M N W substr M N j = U substr M N j
26 nn0re M 0 M
27 nn0re N 0 N
28 ltnle M N M < N ¬ N M
29 ltle M N M < N M N
30 28 29 sylbird M N ¬ N M M N
31 26 27 30 syl2an M 0 N 0 ¬ N M M N
32 31 3ad2ant2 W Word V U Word V M 0 N 0 N W N U ¬ N M M N
33 simpl1l W Word V U Word V M 0 N 0 N W N U M N W Word V
34 simpl2l W Word V U Word V M 0 N 0 N W N U M N M 0
35 6 7 anim12i M 0 N 0 M N
36 35 3ad2ant2 W Word V U Word V M 0 N 0 N W N U M N
37 36 anim1i W Word V U Word V M 0 N 0 N W N U M N M N M N
38 df-3an M N M N M N M N
39 37 38 sylibr W Word V U Word V M 0 N 0 N W N U M N M N M N
40 eluz2 N M M N M N
41 39 40 sylibr W Word V U Word V M 0 N 0 N W N U M N N M
42 34 41 jca W Word V U Word V M 0 N 0 N W N U M N M 0 N M
43 simpl3l W Word V U Word V M 0 N 0 N W N U M N N W
44 swrdlen2 W Word V M 0 N M N W W substr M N = N M
45 33 42 43 44 syl3anc W Word V U Word V M 0 N 0 N W N U M N W substr M N = N M
46 45 oveq2d W Word V U Word V M 0 N 0 N W N U M N 0 ..^ W substr M N = 0 ..^ N M
47 46 raleqdv W Word V U Word V M 0 N 0 N W N U M N j 0 ..^ W substr M N W substr M N j = U substr M N j j 0 ..^ N M W substr M N j = U substr M N j
48 0zd W Word V U Word V M 0 N 0 N W N U 0
49 zsubcl N M N M
50 7 6 49 syl2anr M 0 N 0 N M
51 50 3ad2ant2 W Word V U Word V M 0 N 0 N W N U N M
52 6 adantr M 0 N 0 M
53 52 3ad2ant2 W Word V U Word V M 0 N 0 N W N U M
54 fzoshftral 0 N M M j 0 ..^ N M W substr M N j = U substr M N j i 0 + M ..^ N - M + M [˙i M / j]˙ W substr M N j = U substr M N j
55 48 51 53 54 syl3anc W Word V U Word V M 0 N 0 N W N U j 0 ..^ N M W substr M N j = U substr M N j i 0 + M ..^ N - M + M [˙i M / j]˙ W substr M N j = U substr M N j
56 55 adantr W Word V U Word V M 0 N 0 N W N U M N j 0 ..^ N M W substr M N j = U substr M N j i 0 + M ..^ N - M + M [˙i M / j]˙ W substr M N j = U substr M N j
57 nn0cn N 0 N
58 nn0cn M 0 M
59 addid2 M 0 + M = M
60 59 adantl N M 0 + M = M
61 npcan N M N - M + M = N
62 60 61 oveq12d N M 0 + M ..^ N - M + M = M ..^ N
63 57 58 62 syl2anr M 0 N 0 0 + M ..^ N - M + M = M ..^ N
64 63 3ad2ant2 W Word V U Word V M 0 N 0 N W N U 0 + M ..^ N - M + M = M ..^ N
65 64 adantr W Word V U Word V M 0 N 0 N W N U M N 0 + M ..^ N - M + M = M ..^ N
66 65 raleqdv W Word V U Word V M 0 N 0 N W N U M N i 0 + M ..^ N - M + M [˙i M / j]˙ W substr M N j = U substr M N j i M ..^ N [˙i M / j]˙ W substr M N j = U substr M N j
67 ovex i M V
68 sbceqg i M V [˙i M / j]˙ W substr M N j = U substr M N j i M / j W substr M N j = i M / j U substr M N j
69 csbfv2g i M V i M / j W substr M N j = W substr M N i M / j j
70 csbvarg i M V i M / j j = i M
71 70 fveq2d i M V W substr M N i M / j j = W substr M N i M
72 69 71 eqtrd i M V i M / j W substr M N j = W substr M N i M
73 csbfv2g i M V i M / j U substr M N j = U substr M N i M / j j
74 70 fveq2d i M V U substr M N i M / j j = U substr M N i M
75 73 74 eqtrd i M V i M / j U substr M N j = U substr M N i M
76 72 75 eqeq12d i M V i M / j W substr M N j = i M / j U substr M N j W substr M N i M = U substr M N i M
77 68 76 bitrd i M V [˙i M / j]˙ W substr M N j = U substr M N j W substr M N i M = U substr M N i M
78 67 77 mp1i W Word V U Word V M 0 N 0 N W N U M N i M ..^ N [˙i M / j]˙ W substr M N j = U substr M N j W substr M N i M = U substr M N i M
79 33 42 43 3jca W Word V U Word V M 0 N 0 N W N U M N W Word V M 0 N M N W
80 swrdfv2 W Word V M 0 N M N W i M ..^ N W substr M N i M = W i
81 79 80 sylan W Word V U Word V M 0 N 0 N W N U M N i M ..^ N W substr M N i M = W i
82 simpl1r W Word V U Word V M 0 N 0 N W N U M N U Word V
83 simpl3r W Word V U Word V M 0 N 0 N W N U M N N U
84 82 42 83 3jca W Word V U Word V M 0 N 0 N W N U M N U Word V M 0 N M N U
85 swrdfv2 U Word V M 0 N M N U i M ..^ N U substr M N i M = U i
86 84 85 sylan W Word V U Word V M 0 N 0 N W N U M N i M ..^ N U substr M N i M = U i
87 81 86 eqeq12d W Word V U Word V M 0 N 0 N W N U M N i M ..^ N W substr M N i M = U substr M N i M W i = U i
88 78 87 bitrd W Word V U Word V M 0 N 0 N W N U M N i M ..^ N [˙i M / j]˙ W substr M N j = U substr M N j W i = U i
89 88 ralbidva W Word V U Word V M 0 N 0 N W N U M N i M ..^ N [˙i M / j]˙ W substr M N j = U substr M N j i M ..^ N W i = U i
90 66 89 bitrd W Word V U Word V M 0 N 0 N W N U M N i 0 + M ..^ N - M + M [˙i M / j]˙ W substr M N j = U substr M N j i M ..^ N W i = U i
91 47 56 90 3bitrd W Word V U Word V M 0 N 0 N W N U M N j 0 ..^ W substr M N W substr M N j = U substr M N j i M ..^ N W i = U i
92 91 ex W Word V U Word V M 0 N 0 N W N U M N j 0 ..^ W substr M N W substr M N j = U substr M N j i M ..^ N W i = U i
93 32 92 syld W Word V U Word V M 0 N 0 N W N U ¬ N M j 0 ..^ W substr M N W substr M N j = U substr M N j i M ..^ N W i = U i
94 93 impcom ¬ N M W Word V U Word V M 0 N 0 N W N U j 0 ..^ W substr M N W substr M N j = U substr M N j i M ..^ N W i = U i
95 22 25 94 3bitr2d ¬ N M W Word V U Word V M 0 N 0 N W N U W substr M N = U substr M N i M ..^ N W i = U i
96 16 95 pm2.61ian W Word V U Word V M 0 N 0 N W N U W substr M N = U substr M N i M ..^ N W i = U i