Pagini recente » Cod sursa (job #2268305) | Cod sursa (job #1416461) | Cod sursa (job #2967334) | Cod sursa (job #1891103) | Cod sursa (job #650348)
Cod sursa(job #650348)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void kmp(const string &s,const string &t)
{
int n = t.size() , m = s.size() , v[1005];
int *a = new int[m] , k , i , match = 0;
a[0] = 0;
for(i = 1 , k = 0;i < m;++i)
{
while(k > 0 && s[i] != s[k]) k = a[k-1];
if(s[i] == s[k]) k++;
a[i] = k;
}
for(i = k = 0;i < n;++i)
{
while(k > 0 && t[i] != s[k]) k = a[k-1];
if(t[i] == s[k]) k++;
if(k == m)
{
match < 1000 ? v[match++] = i - m + 1 : match++;
a[k] = a[k-1];
}
}
fout<<match<<'\n';
match = min(match,1000);
for(int i = 0;i<match;++i)
fout<<i<<" ";
}
int main()
{
string a ,b;
fin>>a>>b;
kmp(a,b);
return 0;
}