Pagini recente » Cod sursa (job #1595868) | Cod sursa (job #2752999) | Cod sursa (job #2047893) | Cod sursa (job #1027133) | Cod sursa (job #1816353)
# include <cstdio>
# include <cstring>
# include <vector>
# include <algorithm>
using namespace std;
FILE *f = freopen("strmatch.in", "r", stdin);
FILE *g = freopen("strmatch.out", "w", stdout);
const int L_MAX = 2000010;
char pattern[L_MAX];
char s[L_MAX];
int last[L_MAX];
int total;
vector <int> sol;
void compute_prefix()
{
int k = -1;
last[0] = -1;
for (int i=1; i<strlen(pattern); i++)
{
while (pattern[i] != pattern[k+1] && k != -1)
k = last[k];
if (pattern[i] == pattern[k+1])
{
last[i] = k+1;
k++;
}
else
last[i] = -1;
}
/*for (int i=0; i<strlen(pattern); i++)
printf("%d ", last[i]);*/
}
void solve()
{
int k = -1;
for (int i=0; i<strlen(s); i++)
{
while (s[i] != pattern[k+1] && k != -1)
k = last[k];
if (s[i] == pattern[k+1])
{
k++;
if (k == strlen(pattern) - 1)
{
total ++;
if (total <= 1000)
sol.push_back(i-k);
k = last[k];
}
}
}
printf("%d\n", total);
for (int i=0; i<min(total, 1000); i++)
printf("%d ", sol[i]);
}
void read()
{
scanf("%s\n%s", pattern, s);
}
int main()
{
read();
compute_prefix();
solve();
return 0;
}