Pagini recente » Diferente pentru algoritmiada-2019/runda-maraton/solutii/niciomare intre reviziile 4 si 5 | Monitorul de evaluare | Istoria paginii utilizator/traiansf | Istoria paginii utilizator/calinradu91 | Cod sursa (job #2321885)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char p[2000005], s[2000005];
int n, m, j, v[1005], l[2000005], nsol;
int main()
{
f >> p >> s;
n = strlen(p);
m = strlen(s);
for(int i = n; i >= 1; i--)
p[i] = p[i - 1];
for(int i = m; i >= 1; i--)
s[i] = s[i - 1];
j = l[1] = 0;
for(int i = 2; i <= n; i++)
{
while(j && p[j + 1] != p[i])j = l[j];
if(p[j + 1] == p[i])j++;
l[i] = j;
}
for(int i = 1; i <= m; i++)
{
while(j && p[j + 1] != s[i])j = l[j];
if(p[j + 1] == s[i])j++;
if(j == n)
{
++nsol;
v[nsol] = i - n;
j = l[j];
}
}
g << nsol << '\n';
for(int i = 1; i <= min(1000, nsol); i ++)
g << v[i] << " ";
return 0;
}