Pagini recente » Cod sursa (job #2037000) | Cod sursa (job #2468228) | Cod sursa (job #2232606) | Cod sursa (job #2264998) | Cod sursa (job #627189)
Cod sursa(job #627189)
#include <fstream>
#include <string>
using namespace std;
string s,x;
int pr[1000001],k,prv[1000001];
int n,i,j,pot,xl,sl;
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>x>>s;
for (i=s.length(); i>=1; i--)
s[i]=s[i-1];
for (i=x.length(); i>=1; i--)
x[i]=x[i-1];
xl=x.length();
sl=s.length();
for (i=2; i<=xl; i++) {
k=pr[i-1];
while(k&&x[k+1]!=x[i])
k=pr[k];
if (x[k+1]==x[i])
k++;
pr[i]=k;
}
k=0;
for (i=1;i<=sl;i++) {
while(k&&x[k+1]!=s[i])
k=pr[k];
if (x[k+1]==s[i])
k++;
if (k==xl) {
pot++;
if (pot<=1000)
prv[pot]=i-xl;
}
}
g<<pot<<'\n';
for (i=1; i<=min(pot,1000); i++)
g<<prv[i]<<' ';
g.close();
return 0;
}