Pagini recente » Cod sursa (job #3212214) | Cod sursa (job #1898615) | Cod sursa (job #406625) | Cod sursa (job #1746804) | Cod sursa (job #2042261)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define lim 2000020
int n,m,pref[lim];
char pattern[lim],text[lim];
vector <int> sol;
void prefix_function()
{
for (int i=2; i<=n; i++)
{
int k=pref[i-1];
while (k && pattern[k+1] != pattern[i]) k=pref[k];
if (pattern[k+1] == pattern[i]) k++;
pref[i]=k;
}
}
int main()
{
fin>>(pattern+1)>>(text+1);
n=strlen(pattern+1);
m=strlen(text+1);
prefix_function();
int pos=0;
for (int i=1; i<=m; i++)
{
while (pattern[pos+1] != text[i] && pos) pos=pref[pos];
if (pattern[pos+1] == text[i]) ++pos;
if (pos==n) sol.emplace_back(i-pos+1);
}
int nr=0;
fout<<sol.size()<<'\n';
for (auto x:sol)
{
fout<<x-1<<' ';
if (++nr==1000)
break;
}
fin.close();
fout.close();
return 0;
}