Pagini recente » Cod sursa (job #2526893) | Cod sursa (job #2503638) | Cod sursa (job #1992416) | Cod sursa (job #2275055) | Cod sursa (job #3158577)
#include <bits/stdc++.h>
#define pb push_back
#define NM 2000005
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string a, b;
int lenA, lenB;
int lps[NM];
vector <int> sol;
void makeLps()
{
int i, len = 0;
for(i = 1; i < lenA; i++)
{
if(a[i] == a[len])
{
len++;
lps[i] = len;
}
else if(len > 0)
{
len = lps[len - 1];
i--;
continue;
}
}
}
int main()
{
int i = 0, j = 0;
fin >> a >> b;
lenA = a.size();
lenB = b.size();
makeLps();
while(j < lenB)
{
if(a[i] == b[j])
{
i++;
j++;
if(i == lenA)
{
sol.pb(j - lenA);
i = lps[i - 1];
}
}
else if(i > 0)
i = lps[i - 1];
else
j++;
}
fout << sol.size() << '\n';
for(int x : sol)
fout << x << ' ';
return 0;
}