Pagini recente » Cod sursa (job #1552974) | Cod sursa (job #98866) | Cod sursa (job #569618) | Cod sursa (job #107396) | Cod sursa (job #2434302)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int pref[2000005];
char a[2000005], b[2000005];
int rez[2000005], rez1;
void prefix()
{
int m = strlen(a);
int len = 0;
pref[0] = 0;
for(int i = 1 ; i <= m ; i ++)
{
while( len > 0 && a[i] != a[len]) len = pref[len];
if(a[i] == a[len]) len++;
pref[i] = len;
}
}
void kmp()
{
prefix();
int n = strlen(b);
int m = strlen(a);
int i = 0, j = 0;
while( i < n)
{
if(b[i] == a[j])
i++, j++;
if(j == m)
rez[++rez1] = i - j, j = pref[j - 1];
else if (i < n && b[i] != a[j])
{
if(j > 0)
j = pref[j - 1];
else
i++;
}
}
cout << rez1 << '\n';
(rez1 > 1000) ? rez1 = 1000 : rez1 = rez1;
for(int i = 1 ; i <= rez1 ; i++)
cout << rez[i] << ' ';
}
int main()
{
cin >> a;
cin >> b;
kmp();
return 0;
}