Pagini recente » Cod sursa (job #945607) | Cod sursa (job #2723339) | Cod sursa (job #1099364) | Cod sursa (job #2630588) | Cod sursa (job #2354346)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char s1[2000005], s2[2000005];
int pref[2000005], sz1, sz2, ans[1005], k;
void prefix()
{
int k = 0;
pref[1] = 0;
for(int i = 2; i <= sz1; i++) {
while(k > 0 && s1[k + 1] != s1[i]) k = pref[k];
if(s1[k + 1] == s1[i]) ++k;
pref[i] = k;
}
}
int main()
{
fin.getline(s1 + 1, 2000003);
fin.getline(s2 + 1, 2000003);
sz1 = strlen(s1 + 1);
sz2 = strlen(s2 + 1);
prefix();
int cnt = 0;
for(int i = 1; i <= sz2; i++) {
while(cnt > 0 && s2[i] != s1[cnt + 1]) cnt = pref[cnt];
if(s2[i] == s1[cnt + 1]) ++cnt;
if(cnt == sz1) {
cnt = pref[sz1];
if(k < 1000) ans[++k] = i - sz1;
else ++k;
}
}
fout << k << "\n";
for(int i = 1; i <= min(1000, k); i++) fout << ans[i] << " ";
return 0;
}