Pagini recente » Cod sursa (job #817159) | Cod sursa (job #2430360) | Cod sursa (job #96511) | Cod sursa (job #2382932) | Cod sursa (job #3250289)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int lps[2005], n, m, i, len, j, v[1005], k;
int main()
{
fin>>a>>b;
n=a.size();
m=b.size();
i=1;
lps[0]=0;
while (i<n) {
if (a[i]==a[len]) {
len++;
lps[i]=len;
i++;
}
else {
if (len==0) {
lps[i]=len;
i++;
}
else len=lps[len-1];
}
}
for (i=1; i<n; i++) cout<<lps[i]<<' ';
i=j=0;
while (i<m) {
if (j==n) {
v[++k]=i-n;
if (k==1000) break;
j=lps[j-1];
}
if (b[i]==a[j]) {
i++;
j++;
}
else {
if (j==0) {
i++;
}
j=lps[j-1];
}
}
if (j==n) v[++k]=i-n;
fout<<k<<'\n';
for (i=1; i<=k; i++) fout<<v[i]<<' ';
return 0;
}