这里就没有升级IOS9后没法在itune里面备份app的吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Apple - 家有苹果

这里就没有升级IOS9后没法在itune里面备份app的吗？

这里就没有升级IOS9后没法在itune里面备份app的吗？# Apple - 家有苹果

s*g2015-09-21 07:09

1 楼

刚开始找工作，面试了几家，好几次被问到了这道题，想来应该是经典题了，可是搜了
一下，没发现很直接的答案，所以想请教大家。
题目是：
有一个不定长的char string (S1)，都是0,1组成；另外一个string （S2）, 也是0,1
组成，可以认为是pattern,问S1中是否含有S2
e.g S1 = 11100011 10101011 11111111 10000100 ( 4 bytes, '11100011' is 1 byte)
S2 = 00111010
the answer is ture, 1110"00111010"1011
希望讲清楚了，先谢谢了

O*n2015-09-21 07:09

2 楼

咔嚓后第三天。

qr2015-09-21 07:09

3 楼

有什么可以破解的办法？

j*u2015-09-21 07:09

4 楼

没看懂。
为什么表示成bit？这个难道不就是普通的substring match吗？

O*n2015-09-21 07:09

5 楼

【在 O**********n 的大作中提到】

: 咔嚓后第三天。

x*q2015-09-21 07:09

6 楼

现在大部分都是icloud备份了吧？

【在 qr 的大作中提到】

: 有什么可以破解的办法？

g*s2015-09-21 07:09

7 楼

special string, should be some trick of bit manipulation?

【在 j*****u 的大作中提到】

: 没看懂。
: 为什么表示成bit？这个难道不就是普通的substring match吗？

N*E2015-09-21 07:09

8 楼

麦克斯的精神看起来还不错

t*d2015-09-21 07:09

9 楼

can you just do right shift S1 32 times and check bitwise and with 11111111
and the one of the result should equal s2 if the patten is contained in S1.
assume s2 is already 1 byte.

m*j2015-09-21 07:09

10 楼

爷爷奶奶没给专门做点病号饭？

b*n2015-09-21 07:09

11 楼

didn't notice it's char string not binary bits,
slide a window of len(S2) over S1, and the value of the window
can be calculated at first, then silde the window one char at a time,
the new value will be the old valude << 1 + new added char (constant time)
compare the value of the window with valude of S2
O(n)

1
byte)

【在 s******g 的大作中提到】

: 刚开始找工作，面试了几家，好几次被问到了这道题，想来应该是经典题了，可是搜了
: 一下，没发现很直接的答案，所以想请教大家。
: 题目是：
: 有一个不定长的char string (S1)，都是0,1组成；另外一个string （S2）, 也是0,1
: 组成，可以认为是pattern,问S1中是否含有S2
: e.g S1 = 11100011 10101011 11111111 10000100 ( 4 bytes, '11100011' is 1 byte)
: S2 = 00111010
: the answer is ture, 1110"00111010"1011
: 希望讲清楚了，先谢谢了