Pagini recente » Cod sursa (job #100285) | Cod sursa (job #427039) | Cod sursa (job #2465038) | Cod sursa (job #933495) | Cod sursa (job #639009)
Cod sursa(job #639009)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void kmp_match(const string &t,const string &p)
{
int q = 0 , match = 0 , v[1002];
int n = (int)t.length() , m = (int)p.length();
int *a = new int[m] , k = 0;
a[0] = 0;
for(int q = 1; q < m; q++)
{
while (k > 0 && p[k] != p[q])
k = a[k-1];
if (p[k] == p[q])
k++;
a[q] = k;
}
for (int i = 0; i < n; i++)
{
while(q > 0 && p[q] != t[i])
q = a[q-1];
if (p[q] == t[i])
q++;
if (q == m)
{
if(match<1000) v[match] = i - m + 1;
match++;
q = a[q-1];
}
}
fout<<match<<'\n';
match = min(match,1000);
for(int i=0;i<match;++i)
fout<<v[i]<<" ";
}
int main()
{
string A , B;
fin>>A>>B;
kmp_match(B,A);
return 0;
}