Pagini recente » Cod sursa (job #405019) | Cod sursa (job #1246045) | Cod sursa (job #1490358) | Cod sursa (job #273385) | Cod sursa (job #600979)
Cod sursa(job #600979)
#include <fstream>
#include <string>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
int u[2000000], n, m, i, k, sol[1001], poz=0;
void prefix()
{
u[1]=0;
k=0;
for (i=2; i<n; i++)
{
while (k>0 && a[k+1]!=a[i]) k=u[k];
if (a[k+1]==a[i]) k++;
u[i]=k;
}
}
int kmp()
{
k=0;
for (i=1; i<m; i++)
{
while (k>0 && a[k+1]!=b[i]) k=u[k];
if (a[k+1]==b[i]) k++;
if (k==n-1)
{
poz++;
sol[poz]=i-n+1;
if (poz==1001) return 0;
k=u[k];
}
}
return 0;
}
int main()
{
f >> a >> b;
a=" "+a;
b=" "+b;
n=a.length();
m=b.length();
prefix();
kmp();
g << poz << "\n";
for (i=1; i<=poz; i++)
g << sol[i] << " ";
return 0;
}