Pagini recente » Cod sursa (job #2309181) | Cod sursa (job #1670981) | Cod sursa (job #1754461) | Cod sursa (job #1871195) | Cod sursa (job #3246003)
#include <bits/stdc++.h>
const std :: string FILENAME = "strmatch";
std :: ifstream f (FILENAME + ".in");
std :: ofstream g (FILENAME + ".out");
const int NMAX = 2e6 + 5;
int n;
int cnt;
int pi[NMAX * 2];
std :: string s;
std :: string t;
void kmp()
{
for(int i = 1; i < s.size(); i ++)
{
int j = pi[i - 1];
while(j > 0 && s[i] != s[j])
{
j = pi[j - 1];
}
if(s[i] == s[j])
{
j ++;
}
pi[i] = j;
}
}
int main()
{
f >> t;
s += t;
n = t.size();
s += '#';
f >> t;
s += t;
kmp();
for(int i = 0; i < s.size(); i ++)
{
if(pi[i] == n)
{
cnt ++;
}
}
g << cnt << '\n';
cnt = 0;
for(int i = 0; i < s.size(); i ++)
{
if(pi[i] == n)
{
cnt ++;
std :: cout << i << " ";
g << i - 2 * n << " ";
if(cnt == 1000)
{
return 0;
}
}
}
return 0;
}