Pagini recente » Cod sursa (job #1607203) | Cod sursa (job #2796251) | Cod sursa (job #639008)
Cod sursa(job #639008)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int* genprefix(string p)
{
int m = (int)p.length() , k = 0;
int *a = new int[m+1];
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;
}
return a;
}
void kmp_match(string t, string p)
{
int q = 0 , match = 0 , v[1002];
int n = (int)t.length() , m = (int)p.length();
int *a = genprefix(p);
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;
}