Pagini recente » Cod sursa (job #1645691) | Cod sursa (job #337316) | Cod sursa (job #1884943) | Cod sursa (job #1229123) | Cod sursa (job #1771394)
#include <bits/stdc++.h>
#define NMax 2000003
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char s[2*NMax];
int kmp[2*NMax];
int S,L,ans;
vector<int> A;
int main()
{
f.getline(s,2*NMax);
S = strlen(s);
L = S;
s[S] = '#';
f.getline(s + S + 1,2*NMax);
S = strlen(s);
kmp[0] = 0;
for(int i = 1; i < S; ++i){
int j = kmp[i - 1];
while(j > 0 && s[i] != s[j])
j = kmp[j - 1];
if(s[i] == s[j])
kmp[i] = j + 1;
if(kmp[i] == L){
++ans;
if(ans < 1000)
A.push_back(i - L - L);
}
}
g << ans << '\n';
for(int i = 0; i < A.size(); ++i){
g << A[i] << ' ';
}
return 0;
}