Pagini recente » Cod sursa (job #1215458) | Cod sursa (job #1307456) | Cod sursa (job #2047795) | Cod sursa (job #198030) | Cod sursa (job #2453380)
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#define fs first
#define sc second
#define pii pair <int, int>
#define Nmax 2000005
#define MOD1 666013
#define MOD2 100007
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[Nmax], b[Nmax];
int pr[Nmax], ans;
vector <int> sol;
void prefix(char s[], int len)
{
int j=0;
for (int i = 2; i <= len; i++)
{
while (j!=0 && s[i]!=s[j+1]) j = pr[j];
if (s[i] == s[j+1]) j++;
pr[i]=j;
}
}
int main()
{
f >> a+1 >> b+1;
int la=strlen(a+1), lb=strlen(b+1);
prefix(a, la);
int j=0;
for (int i = 1; i <= lb; i++)
{
while (j!=0 && b[i]!=a[j+1]) j = pr[j];
if (b[i] == a[j+1]) j++;
if (j == la && sol.size() < 1000) sol.push_back(i-la);
}
g << sol.size() << '\n';
for (auto i:sol) g << i << " ";
return 0;
}