Pagini recente » Cod sursa (job #1416836) | Cod sursa (job #105577) | Cod sursa (job #62577) | Cod sursa (job #2845055) | Cod sursa (job #2518447)
#include<bits/stdc++.h>
#define LungMax 2000005
using namespace std;
int i, j, sufix[LungMax], n, m, ans[1005], k;
char s[LungMax], t[LungMax];
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(t, sizeof(t));
f.getline(s, sizeof(s));
n = strlen(s);
m = strlen(t);
j = 0;
i = 1;
while(i < m)
{
if(t[j] == t[i])
{
sufix[i] = j + 1;
j ++;
i ++;
}
else if(j == 0)sufix[i] = 0, i ++;
else j = sufix[j - 1];
}
j = 0;
for(i = 0; i < n; i ++)
if(s[i] == t[j])
{
j ++;
if(j == m)
{
if(k <= 1002)ans[++ k] = i - m + 1, j = sufix[j - 1];
else k ++;
}
}
else if(j == 0)continue;
else j = sufix[j - 1], i --;
g << k << "\n";
for(i = 1; i <= min(k, 1000); i ++)
g << ans[i] << " ";
return 0;
}