Pagini recente » Cod sursa (job #1343541) | Cod sursa (job #1582518) | Cod sursa (job #1007733) | Cod sursa (job #2089549) | Cod sursa (job #2667659)
#include <fstream>
#include <cstring>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pattern[2000001];
void Pattern( string s1, int n)
{
for(int i = 0; i < n; i++)
if(pattern[i + 1] == 0)
for(int j = i + 1; j < n; j++)
if(s1[i] == s1[j])
pattern[j + 1] = i + 1;
}
int main()
{
string s1, s2;
fin >> s1 >> s2;
int l1 = s1.length(), l2 = s2.length(), sol[1000];
Pattern(s1, l1);
int i = 0, j = 0, k = 0, ct = 0;
while(i < l2)
{
int ii = i, jj = j;
while(s2[ii] == s1[jj])
{
ii++;
jj++;
if(jj == l1)
{
k++;
if(ct < 1000)
sol[ct++] = ii - l1;
}
}
i += (pattern[j] + 1);
j = pattern[j];
}
fout << k << '\n';
for(i = 0; i < ct; i++)
fout << sol[i] <<' ';
}