Pagini recente » Cod sursa (job #355605) | Cod sursa (job #2361725) | Cod sursa (job #3197972) | Cod sursa (job #1843231) | Cod sursa (job #2811257)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define cin fin
#define cout fout
#define N 2000005
char a[N], b[N];
int la, lb, nr, i, j, len, lps[N], rez[1005];
int main()
{
cin >> a >> b;
la = strlen(a), lb = strlen(b);
if(la > lb)
{
cout << 0;
return 0;
}
i = 1;
while(i < la)
{
if(a[i] == a[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if(len == 0)
{
lps[i] = 0;
i++;
}
else
{
len = lps[len-1];
}
}
}
i = j = 0;
while(i < lb)
{
if(b[i] == a[j])
{
i++, j++;
}
if(j == la)
{
nr++;
if(nr <= 1000)rez[nr] = i-la;
j = lps[j-1];
}
else if(i < lb && b[i] != a[j])
{
if(j == 0)
{
i++;
}
else
{
j = lps[j-1];
}
}
}
cout << nr << '\n';
for(int i = 1 ; i <= nr && i <= 1000 ; i++)
{
cout << rez[i] << " ";
}
return 0;
}