Comparing 2 strings

[Kalcor]

Hello today I came across this:

Given 2 strings a and b find the indices of the characters in A to be changed so that it becomes a substring of B, and its guaranteed to have an answer.

I had a few mistakes implementing it then I figured out the fix to my mistakes in which i don't understand so I hope someone helps me understand them.

first here are a few sample inputs:

input
3 5
abc
xaybz

output
2
2 3
---------
input
4 10
abcd
ebceabazcd

output
1
2

First 2 integers in the input are the sizes of A and B. The output is basically the 1 index-ed part of string A that needs to be changed in order to be a substring of B.

my implementation(after fixing it):

#include <bits/stdc++.h>


#define fl(i,n)    for(int i = 0; i < n; i++)

#define ll   long long
#define nl   endl
#define pb   push_back
#define mp   make_pair
#define PII  pair<int,int>

#define EPS  1e-9
#define INF  1e16


using namespace std;


int main()
{
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;

    int pos;
    vector<int> c, ans;
    ans.resize(10000);

    for(int i = 0; i <= m-n; i++){
        c.clear();
        pos = 0;
        for(int j = 0; j < n; j++){
            if(t[j+i] != s[j]) {
                pos++;
                c.pb(j);
            }
        }

        if(ans.size() > pos){
            ans = c;
        }
    }
    cout << ans.size() << nl;
    for(auto x: ans) cout << x+1 << " ";





    return 0;
}

Here are the parts I don't get:
1. The outer loop condition:
for(int i = 0; i <= m-n; i++)
Why is it m-n ? why not n or why not m? I got a wrong answer on more than one of the testcases due to having the loop set to i < m instead of i <= m-n.

2. The if condition in the middle:
if(t[j+i] != s[j])
What does "j+i" represent?


Thanks!

[lastchance]

It is probably easiest if you imagine A (the smaller string) being placed under B and shifted along, comparing its characters at each step.

A displaced i = 0 positions ...

   ijklmnopqrstuvwxyz     - string B (m chars)
   abcdefg                - string A (n chars)
   |__n__||___m-n___|
 



A displaced i = 1 position ...

   ijklmnopqrstuvwxyz   
    abcdefg             

 


A displaced i = 2 positions ...

   ijklmnopqrstuvwxyz   
     abcdefg

 


A displaced m-n positions ... (the last comparison)

   ijklmnopqrstuvwxyz   
              abcdefg

Index i is the amount by which you have shifted string A across underneath B. From the (attempted) diagram above you need to start with i = 0 and finish with i = m - n.

2. The if condition in the middle:
if(t[j+i] != s[j])
What does "j+i" represent?

j is the position in the lower string (A in my example, s[] in the code).
j+i is the position in the upper string: once A has been shifted across i places, the first i elements of B are ignored in the comparison. The jth element of A is being compared with the (i+j)th element of B.



Here's a generic version for any container, not just strings. Note that the reported indices are numbered from 0 rather than the 1 used in your code.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

//======================================================================

template <class C> int minDifference( const C &shorter, const C &longer, vector<int> &indices )     // generic containers of type C
{
   int m = longer.size();
   int n = shorter.size();
   indices.clear();
   if ( m < n || n == 0 ) return -1;            // impossible cases

   int minimum = n + 1;

   for ( int i = 0; i <= m - n; i++ )           // successive displacements along longer container
   {
      vector<int> temp;
      for ( int j = 0; j < n; j++ ) if ( longer[i+j] != shorter[j] ) temp.push_back( j );
      if ( temp.size() < minimum )
      {
         minimum = temp.size();
         indices = temp;
         if ( minimum == 0 ) return 0;          // early exit if a subsequence
      }
   }
   return minimum;
}

//======================================================================

int main()
{
   vector<int> indices;
   int minDiff;

   string A = "abc", B = "xaybz";
// string A = "abcd", B = "ebceabazcd";
// vector<int> A = { 1, 2, 3 }, B = { 1, 3, 5, 7, 7 };

   minDiff = minDifference( A, B, indices );
   cout << "Minimum difference: " << minDiff;
   if ( minDiff != 0 ) 
   {
      cout << " at indices: ";
      for ( int i : indices ) cout << i << " ";   
   }
   cout << '\n';
}

[Enoizat]

Your code is wonderful, lastchance.
Only a looser like me could point out that there's still a container which doesn't have a size() method (forward_list). Apart from that, it works like a charm.

[lastchance]

Ah cheers @Enoizat - it's a good point! I'll see what I can come up with.

[Kalcor]

@lastchance this code is meant to solve the exact same task ?

[gunnerfunner]

Hi lastchance, re Enoziat's you might have probably thought of something already far superior to what follows, in which case apols in advance:

#include <iostream>
#include <string>
#include <vector>
#include <type_traits>
#include <forward_list>
using namespace std;

//======================================================================

template <class C> void minDifference( const C &shorter, const C &longer, vector<int> &indices )    
// generic containers of type C
{
   static_assert(std::is_member_function_pointer<decltype(&C::size)>::value,
                  "size() is not a member function.");
   std::cout << "ok \n";
}

//======================================================================

int main()
{
   vector<int> indices;
   int minDiff;

   string A = "abc", B = "xaybz";
   std::forward_list<std::string> a{}, b{};

   minDifference( A, B, indices );
   minDifference(a, b, indices);
}

This, at least, forces the program to fail at compile time. The other alternative might be to explicitly specialize minDifference() for std::forward_list if that is feasible

[lastchance]

@kalcor,
The majority of my post was to answer your original question: which I hope that it did. The code gives a templated function to explain and generalise it - not answer a question on codeforces.com, since I assume that your original code did that. As long as you write the input and output parts you can call the templated function to solve your problem. Note that I have indexed indices from 0, rather than 1 as in your post - you can easily use +1 when outputting.

@Enoizat and @gunnerfunner - thank you for your contributions. Realistically I suspect the code is really only useful for strings, vectors and objects for which size() and [] indexing are defined. "Any" container was rather overstated - as @enoizat pointed out.

[ne555]

> This, at least, forces the program to fail at compile time.
that was already happening in the original code.

[gunnerfunner]

> This, at least, forces the program to fail at compile time.
that was already happening in the original code.

in the original code, yes, but not without the static_assert in the (albeit, contrived) program in my post – this actually raises a broader query in my mind – when templating over containers how does one check presence/absence vis-a-vis member methods, data members and operators?

[lastchance]

Here you go, @kalcor. You can try it on codeforces.com.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

//======================================================================

template <class C> int minDifference( const C &shorter, const C &longer, vector<int> &indices )     // generic containers of type C
{
   int m = longer.size();
   int n = shorter.size();
   indices.clear();
   if ( m < n || n == 0 ) return -1;            // impossible cases

   int minimum = n + 1;

   for ( int i = 0; i <= m - n; i++ )           // successive displacements along longer container
   {
      vector<int> temp;
      for ( int j = 0; j < n; j++ ) if ( longer[i+j] != shorter[j] ) temp.push_back( j );
      if ( temp.size() < minimum )
      {
         minimum = temp.size();
         indices = temp;
         if ( minimum == 0 ) return 0;          // early exit if a subsequence
      }
   }
   return minimum;
}

//======================================================================

int main()
{
   vector<int> indices;
   int m, n;
   string A, B;

   cin >> m >> n >> A >> B;                         // m and n actually redundant here
   cout << minDifference( A, B, indices ) << '\n';
   for ( int i : indices ) cout << i + 1 << " ";    // counting indices from 1, not 0
}

[Kalcor]

@lastchance thank you <3